Submission #5897806
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 | 0 |
Code Size | 1681 Byte |
Status | RE |
Exec Time | 174 ms |
Memory | 38256 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 | 169 ms | 38256 KB |
subtask0_sample02.txt | RE | 167 ms | 38256 KB |
subtask0_sample03.txt | RE | 169 ms | 38256 KB |
subtask1_01.txt | RE | 168 ms | 38256 KB |
subtask1_02.txt | RE | 165 ms | 38256 KB |
subtask1_03.txt | RE | 163 ms | 38256 KB |
subtask1_04.txt | RE | 174 ms | 38256 KB |
subtask1_05.txt | RE | 167 ms | 38256 KB |
subtask1_06.txt | RE | 166 ms | 38256 KB |
subtask1_07.txt | RE | 169 ms | 38256 KB |
subtask1_08.txt | RE | 169 ms | 38256 KB |
subtask1_09.txt | RE | 169 ms | 38256 KB |
subtask1_10.txt | RE | 168 ms | 38256 KB |
subtask1_11.txt | RE | 169 ms | 38256 KB |
subtask1_12.txt | RE | 168 ms | 38256 KB |
subtask2_01.txt | RE | 170 ms | 38256 KB |
subtask2_02.txt | RE | 164 ms | 38256 KB |
subtask2_03.txt | RE | 163 ms | 38256 KB |
subtask2_04.txt | RE | 173 ms | 38256 KB |
subtask2_05.txt | RE | 164 ms | 38256 KB |
subtask2_06.txt | RE | 169 ms | 38256 KB |
subtask2_07.txt | RE | 166 ms | 38256 KB |
subtask2_08.txt | RE | 169 ms | 38256 KB |
subtask2_09.txt | RE | 168 ms | 38256 KB |
subtask2_10.txt | RE | 169 ms | 38256 KB |
subtask2_11.txt | RE | 166 ms | 38256 KB |
subtask2_12.txt | RE | 166 ms | 38256 KB |