Submission #5897819
Source Code Expand
class Lca: def __init__(self, E, root): import sys sys.setrecursionlimit(500000) self.root = root self.E = E # V<V> self.n = len(E) # 頂点数 self.logn = 1 while self.n >= (1<<self.logn): self.logn += 1 self.parent = [[-1]*self.n for _ in range(self.logn)] self.depth = [0] * self.n self.dfs(root, -1, 0) for k in range(self.logn-1): for v in range(self.n): p_ = self.parent[k][v] if p_ >= 0: self.parent[k+1][v] = self.parent[k][p_] def dfs(self, v, p, dep): self.parent[0][v] = p self.depth[v] = dep for e in self.E[v]: if e != p: self.dfs(e, v, dep+1) def get(self, u, v): if self.depth[u] > self.depth[v]: u, v = v, u dep_diff = self.depth[v]-self.depth[u] for k in range(self.logn): if dep_diff >> k & 1: v = self.parent[k][v] if u==v: return u for k in range(self.logn-1, -1, -1): if self.parent[k][u] != self.parent[k][v]: u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u] N = int(input()) xy = {} for i in range(N): xy[i] = [] for i in range(N-1): x,y = map(int,input().split()) xy[x-1].append(y-1) xy[y-1].append(x-1) lca = Lca(xy,0) Q = int(input()) for i in range(Q): a,b = map(int,input().split()) q = lca.get(a-1,b-1) print(lca.depth[a-1] + lca.depth[b-1] - 2*lca.depth[q] + 1)
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | alexara1123 |
Language | PyPy3 (2.4.0) |
Score | 30 |
Code Size | 1680 Byte |
Status | TLE |
Exec Time | 2024 ms |
Memory | 163940 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 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 | 163 ms | 38384 KB |
subtask0_sample02.txt | AC | 161 ms | 38256 KB |
subtask0_sample03.txt | AC | 163 ms | 38256 KB |
subtask1_01.txt | AC | 884 ms | 157284 KB |
subtask1_02.txt | AC | 867 ms | 155108 KB |
subtask1_03.txt | AC | 163 ms | 38256 KB |
subtask1_04.txt | AC | 167 ms | 38256 KB |
subtask1_05.txt | AC | 212 ms | 41072 KB |
subtask1_06.txt | AC | 204 ms | 40176 KB |
subtask1_07.txt | AC | 727 ms | 79972 KB |
subtask1_08.txt | AC | 770 ms | 85092 KB |
subtask1_09.txt | AC | 769 ms | 88804 KB |
subtask1_10.txt | AC | 796 ms | 90340 KB |
subtask1_11.txt | AC | 803 ms | 94436 KB |
subtask1_12.txt | AC | 793 ms | 94308 KB |
subtask2_01.txt | AC | 1768 ms | 163940 KB |
subtask2_02.txt | AC | 1795 ms | 163812 KB |
subtask2_03.txt | AC | 1187 ms | 55640 KB |
subtask2_04.txt | AC | 1209 ms | 55384 KB |
subtask2_05.txt | AC | 1252 ms | 59352 KB |
subtask2_06.txt | AC | 1220 ms | 60124 KB |
subtask2_07.txt | AC | 1981 ms | 99428 KB |
subtask2_08.txt | AC | 1942 ms | 96484 KB |
subtask2_09.txt | AC | 1968 ms | 99300 KB |
subtask2_10.txt | AC | 1979 ms | 102884 KB |
subtask2_11.txt | AC | 2000 ms | 105480 KB |
subtask2_12.txt | TLE | 2024 ms | 105188 KB |