Submission #7488663
Source Code Expand
def resolve(): class LCA(object): def __init__(self,edges,root): self.edges=edges self.root=root self.n=len(edges) # n=|V| # self.logn=(self.n-1).bit_length() # logn = ceil(log2(n)) self.logn=18 # logn = ceil(log2(n)) # initialization self.depth=[float("inf") if i!=root else 0 for i in range(self.n)] self.parent=[[-1]*(self.logn+1) for _ in range(self.n)] # parent[u][i]=v : uの2^i世代上がv(なければ-1) # construct self.dfs(root) self.doubling() def dfs(self,u): for v in self.edges[u]: if self.depth[v]==float("inf"): # 訪れていない=深さがINF(rootから連結な部分しか探索しない) self.depth[v]=self.depth[u]+1 self.parent[v][0]=u self.dfs(v) def doubling(self): for i in range(1,self.logn): for v in range(self.n): if self.parent[v][i-1]!=-1: # 半分遡った時点で親が存在しなければ-1のままにしておく。-1が返るとlistの末尾の値の取得になってしまう self.parent[v][i]=self.parent[self.parent[v][i-1]][i-1] def get(self,u,v): # uとvとのLCAを返す dd=self.depth[v]-self.depth[u] if dd<0: # vの方が深いようにする u,v=v,u dd=-dd for i in range(self.logn): # dd分だけvを遡らせる if dd&1<<i: # 各bitで判定 v=self.parent[v][i] if u==v: return u # 高さ揃えた時点で一致してたら終わり for i in range(self.logn-1,-1,-1): # そうでなければ上から二分探索 pu,pv=self.parent[u][i],self.parent[v][i] if pu!=pv: u,v=pu,pv # 高さが一致してるので、片方だけ-1ということはない return self.parent[u][0] #%% # given data N=int(input()) E=[set() for _ in range(N)] root=0 for _ in range(N-1): u,v=map(lambda x:int(x)-1,input().split()) E[u].add(v) E[v].add(u) lca=LCA(E,root) Q=int(input()) for _ in range(Q): u,v=map(lambda x:int(x)-1,input().split()) print(lca.depth[u]+lca.depth[v]-2*lca.depth[lca.get(u,v)]+1) resolve()
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | moni0627 |
Language | PyPy3 (2.4.0) |
Score | 0 |
Code Size | 2494 Byte |
Status | RE |
Exec Time | 2111 ms |
Memory | 128004 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 | 170 ms | 38256 KB |
subtask0_sample02.txt | AC | 174 ms | 38256 KB |
subtask0_sample03.txt | AC | 176 ms | 38256 KB |
subtask1_01.txt | RE | 800 ms | 99232 KB |
subtask1_02.txt | RE | 745 ms | 99232 KB |
subtask1_03.txt | AC | 174 ms | 38256 KB |
subtask1_04.txt | AC | 180 ms | 38512 KB |
subtask1_05.txt | AC | 233 ms | 42972 KB |
subtask1_06.txt | AC | 224 ms | 40688 KB |
subtask1_07.txt | AC | 1017 ms | 105248 KB |
subtask1_08.txt | AC | 1024 ms | 105760 KB |
subtask1_09.txt | AC | 1054 ms | 110112 KB |
subtask1_10.txt | AC | 1087 ms | 114720 KB |
subtask1_11.txt | AC | 1091 ms | 111648 KB |
subtask1_12.txt | AC | 1078 ms | 118560 KB |
subtask2_01.txt | RE | 793 ms | 99232 KB |
subtask2_02.txt | RE | 757 ms | 99232 KB |
subtask2_03.txt | AC | 1208 ms | 56664 KB |
subtask2_04.txt | AC | 1331 ms | 57688 KB |
subtask2_05.txt | AC | 1387 ms | 61548 KB |
subtask2_06.txt | AC | 1412 ms | 58200 KB |
subtask2_07.txt | TLE | 2111 ms | 122720 KB |
subtask2_08.txt | TLE | 2111 ms | 120992 KB |
subtask2_09.txt | TLE | 2111 ms | 122912 KB |
subtask2_10.txt | TLE | 2111 ms | 127648 KB |
subtask2_11.txt | TLE | 2110 ms | 128004 KB |
subtask2_12.txt | TLE | 2110 ms | 122016 KB |