Submission #2520715
Source Code Expand
import sys sys.setrecursionlimit(10 ** 7) N = int(input()) G = [[] for i in range(N)] for i in range(N-1): x, y = map(int, sys.stdin.readline().split()) x, y = x-1, y-1 G[x].append(y) G[y].append(x) parent = [[] for i in range(N)] # 親を2^k回辿って到達する頂点 depth = [None] * N stack = [] def walk(i): rec_size = len(stack) depth[i] = rec_size # 親を2^k回辿る k = 0 while 2**k <= rec_size: parent[i].append(stack[rec_size-2**k]) k += 1 stack.append(i) for ni in G[i]: if depth[ni] is not None: continue walk(ni) del stack[-1] walk(0) Q = int(input()) for i in range(Q): a, b = map(int, sys.stdin.readline().split()) a, b = a-1, b-1 if depth[a] > depth[b]: # 深いほうが後ろ a, b = b, a depth_add = depth[a] + depth[b] depth_diff = depth[b] - depth[a] while depth_diff > 0: k = 1 while 2**k < depth_diff: k += 1 k -= 1 b = parent[b][k] depth_diff -= 2**k while a != b: k = 1 le = len(parent[a]) while le > k and parent[a][k] != parent[b][k]: k += 1 k -= 1 a = parent[a][k] b = parent[b][k] print(depth_add - 2*depth[a] + 1)
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | AT274 |
Language | PyPy3 (2.4.0) |
Score | 100 |
Code Size | 1379 Byte |
Status | AC |
Exec Time | 1621 ms |
Memory | 162736 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 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 | 166 ms | 38512 KB |
subtask0_sample02.txt | AC | 162 ms | 38256 KB |
subtask0_sample03.txt | AC | 164 ms | 38256 KB |
subtask1_01.txt | AC | 1186 ms | 158384 KB |
subtask1_02.txt | AC | 1201 ms | 158384 KB |
subtask1_03.txt | AC | 165 ms | 38256 KB |
subtask1_04.txt | AC | 163 ms | 38256 KB |
subtask1_05.txt | AC | 189 ms | 41052 KB |
subtask1_06.txt | AC | 188 ms | 41324 KB |
subtask1_07.txt | AC | 447 ms | 71840 KB |
subtask1_08.txt | AC | 442 ms | 70064 KB |
subtask1_09.txt | AC | 508 ms | 72752 KB |
subtask1_10.txt | AC | 498 ms | 76720 KB |
subtask1_11.txt | AC | 623 ms | 77360 KB |
subtask1_12.txt | AC | 481 ms | 73648 KB |
subtask2_01.txt | AC | 1605 ms | 162608 KB |
subtask2_02.txt | AC | 1621 ms | 162736 KB |
subtask2_03.txt | AC | 419 ms | 57436 KB |
subtask2_04.txt | AC | 476 ms | 58840 KB |
subtask2_05.txt | AC | 518 ms | 55900 KB |
subtask2_06.txt | AC | 622 ms | 63064 KB |
subtask2_07.txt | AC | 845 ms | 85664 KB |
subtask2_08.txt | AC | 827 ms | 82992 KB |
subtask2_09.txt | AC | 919 ms | 89776 KB |
subtask2_10.txt | AC | 952 ms | 90800 KB |
subtask2_11.txt | AC | 1028 ms | 99504 KB |
subtask2_12.txt | AC | 921 ms | 87728 KB |