Submission #2554941
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; namespace Abc070d { class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); List<Branch> branches = new List<Branch>(); for (int i = 0; i < n - 1; i++) { string[] input = Console.ReadLine().Split(' '); branches.Add(new Branch(int.Parse(input[0]), int.Parse(input[1]), int.Parse(input[2]))); } string[] query = Console.ReadLine().Split(' '); int qNum = int.Parse(query[0]); int k = int.Parse(query[1]); Point[] points = new Point[n + 1]; for (int i = 0; i < n; i++) { points[i + 1] = new Point(); } foreach (Branch branch in branches) { points[branch.From].Add(branch); points[branch.To].Add(branch); } long[] dp = new long[n + 1]; dp[k] = 0; List<int> queue = new List<int>(); queue.Add(k); while (queue.Count > 0) { int current = queue[0]; queue.RemoveAt(0); Point found = points[current]; foreach (Branch branch in found) { int other = branch.other(current); if (dp[other] != 0) { continue; } dp[other] = dp[current] + branch.Distance; queue.Add(other); } } for (int i = 0; i < qNum; i++) { string[] q = Console.ReadLine().Split(' '); int x = int.Parse(q[0]); int y = int.Parse(q[1]); Console.WriteLine(dp[x] + dp[y]); } } } class Point : List<Branch> { } class Branch { public readonly int From; public readonly int To; public readonly int Distance; public Branch(int from, int to, int distance) { From = from; To = to; Distance = distance; } public int other(int current) { if (current == From) { return To; } if (current == To) { return From; } throw new Exception(); } } }
Submission Info
Submission Time | |
---|---|
Task | D - Transit Tree Path |
User | katand |
Language | C# (Mono 4.6.2.0) |
Score | 400 |
Code Size | 2678 Byte |
Status | AC |
Exec Time | 1578 ms |
Memory | 39576 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 22 ms | 11220 KB |
sample_02.txt | AC | 22 ms | 9172 KB |
sample_03.txt | AC | 22 ms | 13268 KB |
subtask_1_1.txt | AC | 22 ms | 11220 KB |
subtask_1_10.txt | AC | 444 ms | 16068 KB |
subtask_1_11.txt | AC | 26 ms | 9300 KB |
subtask_1_12.txt | AC | 58 ms | 11348 KB |
subtask_1_13.txt | AC | 156 ms | 13520 KB |
subtask_1_14.txt | AC | 22 ms | 11220 KB |
subtask_1_15.txt | AC | 32 ms | 13292 KB |
subtask_1_16.txt | AC | 924 ms | 33988 KB |
subtask_1_17.txt | AC | 881 ms | 31940 KB |
subtask_1_18.txt | AC | 913 ms | 33984 KB |
subtask_1_19.txt | AC | 910 ms | 36036 KB |
subtask_1_2.txt | AC | 25 ms | 13332 KB |
subtask_1_20.txt | AC | 876 ms | 35904 KB |
subtask_1_21.txt | AC | 853 ms | 33852 KB |
subtask_1_22.txt | AC | 862 ms | 33856 KB |
subtask_1_23.txt | AC | 858 ms | 33852 KB |
subtask_1_24.txt | AC | 1567 ms | 35608 KB |
subtask_1_25.txt | AC | 1578 ms | 35480 KB |
subtask_1_26.txt | AC | 1564 ms | 35484 KB |
subtask_1_27.txt | AC | 1565 ms | 39576 KB |
subtask_1_28.txt | AC | 843 ms | 32776 KB |
subtask_1_3.txt | AC | 518 ms | 31148 KB |
subtask_1_4.txt | AC | 23 ms | 11220 KB |
subtask_1_5.txt | AC | 581 ms | 16424 KB |
subtask_1_6.txt | AC | 105 ms | 20556 KB |
subtask_1_7.txt | AC | 490 ms | 16192 KB |
subtask_1_8.txt | AC | 22 ms | 11220 KB |
subtask_1_9.txt | AC | 374 ms | 33756 KB |