Submission #1708245
Source Code Expand
import math N = int(input()) C = [[] for _ in range(N)] for _ in range(N - 1): x, y = [int(_) - 1 for _ in input().split()] C[x].append(y) C[y].append(x) log_N = int(math.log2(N)) + 1 dbl = [[-1] * log_N for _ in range(N)] dep = [0] * N # initialize queue = [(0, -1, 0)] # (node, parent, depth), root: 0 while len(queue) > 0: node, parent, depth = queue.pop() dep[node] = depth for edge in C[node]: if edge == parent: continue dbl[edge][0] = node queue.append((edge, node, depth + 1)) # doubling for j in range(1, log_N): for i in range(N): if dbl[i][j-1] == -1: continue dbl[i][j] = dbl[dbl[i][j-1]][j-1] j += 1 def LCA(a, b): def func(leaf, d): res = leaf for i in range(log_N): if (d >> i) & 1: res = dbl[res][i] i += 1 return res if dep[a] > dep[b]: a, b = b, a _a, _b = a, func(b, dep[b] - dep[a]) if _a == _b: return _a else: for i in range(log_N - 1, -1, -1): if dbl[_a][i] != dbl[_b][i]: _a = dbl[_a][i] _b = dbl[_b][i] return dbl[_a][0] # main Q = int(input()) for _ in range(Q): a, b = [int(_) - 1 for _ in input().split()] print(dep[a] + dep[b] - 2 * dep[LCA(a, b)] + 1)
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | yuhi87star |
Language | PyPy3 (2.4.0) |
Score | 0 |
Code Size | 1437 Byte |
Status | RE |
Exec Time | 739 ms |
Memory | 57248 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 | RE | 179 ms | 38640 KB |
subtask0_sample02.txt | RE | 174 ms | 38256 KB |
subtask0_sample03.txt | RE | 172 ms | 38256 KB |
subtask1_01.txt | RE | 626 ms | 57248 KB |
subtask1_02.txt | RE | 605 ms | 56096 KB |
subtask1_03.txt | RE | 171 ms | 38256 KB |
subtask1_04.txt | RE | 176 ms | 38256 KB |
subtask1_05.txt | RE | 211 ms | 39152 KB |
subtask1_06.txt | RE | 211 ms | 39152 KB |
subtask1_07.txt | RE | 641 ms | 56992 KB |
subtask1_08.txt | RE | 632 ms | 56736 KB |
subtask1_09.txt | RE | 637 ms | 56736 KB |
subtask1_10.txt | RE | 647 ms | 56608 KB |
subtask1_11.txt | RE | 681 ms | 56736 KB |
subtask1_12.txt | RE | 646 ms | 56864 KB |
subtask2_01.txt | RE | 585 ms | 56096 KB |
subtask2_02.txt | RE | 583 ms | 56096 KB |
subtask2_03.txt | RE | 174 ms | 38256 KB |
subtask2_04.txt | RE | 175 ms | 38256 KB |
subtask2_05.txt | RE | 212 ms | 39152 KB |
subtask2_06.txt | RE | 213 ms | 39152 KB |
subtask2_07.txt | RE | 665 ms | 56992 KB |
subtask2_08.txt | RE | 703 ms | 56992 KB |
subtask2_09.txt | RE | 703 ms | 56608 KB |
subtask2_10.txt | RE | 723 ms | 56608 KB |
subtask2_11.txt | RE | 739 ms | 56768 KB |
subtask2_12.txt | RE | 660 ms | 56608 KB |