Submission #1294737
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; static class Program { static void Main() { new Magatro().Solve(); } } class Node { public int Num;//いるかな? public List<int> Parent = new List<int>();//Parent[i] 2^i個上 public int Depth; } class Magatro { private int N; List<int>[] R; Node[] Tree; private int Q; private void MakeTree() { Tree = new Node[N]; for (int i = 0; i < N; i++) { Tree[i] = new Node(); Tree[i].Num = i; } Tree[0].Num = 0; Tree[0].Depth = 0; Queue<int> q = new Queue<int>(); q.Enqueue(0); while (q.Count > 0)//木 { int d = q.Dequeue(); foreach (int i in R[d]) { if (Tree[d].Parent.Count > 0 && i == Tree[d].Parent[0]) { continue; } Tree[i].Parent.Add(d); Tree[i].Depth = Tree[d].Depth + 1; q.Enqueue(i); } } for (int i = 1; i < N; i <<= 1)//2^kこ前 { foreach (var n in Tree) { if (n.Depth >= i * 2) { n.Parent.Add(Tree[n.Parent[i / 2]].Parent[i / 2]); } } } } private int Query(int a, int b) { int res = 0; if (Tree[a].Depth > Tree[b].Depth) { a ^= b; b ^= a; a ^= b; } int sa = Tree[b].Depth - Tree[a].Depth; for (int i = 0; sa > 0; sa /= 2, i++)//高さ合わせる { if (sa % 2 == 1) { b = Tree[b].Parent[i]; res += 1 << i; } } if (a == b) { return res; } while (true) { int j = -1; for (int i = 0; i < Tree[a].Parent.Count; i++) { if (Tree[a].Parent[i] == Tree[b].Parent[i]) { break; } j = i; } if(j == -1) { res += 2; break; } else { a = Tree[a].Parent[j]; b = Tree[b].Parent[j]; res += 1 << (j+1); } } return res; } public void Solve() { N = int.Parse(Console.ReadLine()); R = new List<int>[N]; for (int i = 0; i < N; i++) { R[i] = new List<int>(); } for (int i = 0; i < N - 1; i++) { var line = Console.ReadLine().Split(' '); int x = int.Parse(line[0]) - 1; int y = int.Parse(line[1]) - 1; R[x].Add(y); R[y].Add(x); } MakeTree(); Q = int.Parse(Console.ReadLine()); for (int i = 0; i < Q; i++) { var line = Console.ReadLine().Split(' '); int a = int.Parse(line[0]) - 1; int b = int.Parse(line[1]) - 1; Console.WriteLine(Query(a, b) + 1); } } }
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | mban |
Language | C# (Mono 4.6.2.0) |
Score | 0 |
Code Size | 3389 Byte |
Status | RE |
Exec Time | 682 ms |
Memory | 40164 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 70 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample01.txt | AC | 26 ms | 11604 KB |
subtask0_sample02.txt | AC | 24 ms | 11348 KB |
subtask0_sample03.txt | AC | 24 ms | 11348 KB |
subtask1_01.txt | RE | 175 ms | 36972 KB |
subtask1_02.txt | RE | 163 ms | 38688 KB |
subtask1_03.txt | AC | 23 ms | 11348 KB |
subtask1_04.txt | AC | 23 ms | 11348 KB |
subtask1_05.txt | RE | 24 ms | 10848 KB |
subtask1_06.txt | RE | 24 ms | 8928 KB |
subtask1_07.txt | RE | 231 ms | 36068 KB |
subtask1_08.txt | RE | 229 ms | 34196 KB |
subtask1_09.txt | RE | 227 ms | 37100 KB |
subtask1_10.txt | RE | 221 ms | 36972 KB |
subtask1_11.txt | RE | 216 ms | 36972 KB |
subtask1_12.txt | RE | 226 ms | 34924 KB |
subtask2_01.txt | RE | 162 ms | 36640 KB |
subtask2_02.txt | RE | 162 ms | 32876 KB |
subtask2_03.txt | AC | 657 ms | 15680 KB |
subtask2_04.txt | AC | 682 ms | 15804 KB |
subtask2_05.txt | RE | 24 ms | 8928 KB |
subtask2_06.txt | RE | 24 ms | 10848 KB |
subtask2_07.txt | RE | 229 ms | 40164 KB |
subtask2_08.txt | RE | 247 ms | 35160 KB |
subtask2_09.txt | RE | 219 ms | 39016 KB |
subtask2_10.txt | RE | 221 ms | 36776 KB |
subtask2_11.txt | RE | 216 ms | 34924 KB |
subtask2_12.txt | RE | 220 ms | 36972 KB |