Submission #1294735
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 i = 0; bool flag = false; for (; i < Tree[a].Parent.Count; i++) { if (Tree[a].Parent[i] == Tree[b].Parent[i]) { break; flag = true; } } if (i == 0) { res += 2; break; } else { if (!flag) { i--; } a = Tree[a].Parent[i]; b = Tree[b].Parent[i]; res += 1 << (i); } } 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 | 3509 Byte |
Status | RE |
Exec Time | 677 ms |
Memory | 36972 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 | 23 ms | 9300 KB |
subtask0_sample02.txt | AC | 23 ms | 11348 KB |
subtask0_sample03.txt | WA | 23 ms | 11348 KB |
subtask1_01.txt | RE | 164 ms | 34924 KB |
subtask1_02.txt | RE | 161 ms | 34592 KB |
subtask1_03.txt | AC | 23 ms | 11348 KB |
subtask1_04.txt | WA | 24 ms | 13396 KB |
subtask1_05.txt | RE | 24 ms | 10848 KB |
subtask1_06.txt | RE | 23 ms | 8800 KB |
subtask1_07.txt | RE | 235 ms | 36904 KB |
subtask1_08.txt | RE | 228 ms | 35160 KB |
subtask1_09.txt | RE | 220 ms | 34924 KB |
subtask1_10.txt | RE | 220 ms | 34924 KB |
subtask1_11.txt | RE | 221 ms | 36972 KB |
subtask1_12.txt | RE | 221 ms | 34924 KB |
subtask2_01.txt | RE | 164 ms | 34924 KB |
subtask2_02.txt | RE | 164 ms | 34592 KB |
subtask2_03.txt | WA | 659 ms | 17728 KB |
subtask2_04.txt | WA | 677 ms | 13628 KB |
subtask2_05.txt | RE | 23 ms | 8800 KB |
subtask2_06.txt | RE | 24 ms | 10848 KB |
subtask2_07.txt | RE | 228 ms | 36068 KB |
subtask2_08.txt | RE | 227 ms | 36244 KB |
subtask2_09.txt | RE | 218 ms | 36972 KB |
subtask2_10.txt | RE | 228 ms | 36972 KB |
subtask2_11.txt | RE | 220 ms | 36972 KB |
subtask2_12.txt | RE | 218 ms | 33004 KB |