Submission #7490818
Source Code Expand
import sys sys.setrecursionlimit(10**8) def resolve(): import math class DoublingLCA: """ construct: O(NlogN) query O(logN) """ def __init__(self,edges,root=0): """ :param list of (list of int) edges: :param int root=0: """ self.edges = edges self.n = len(edges) self.root = root self.logn = (self.n-1).bit_length() self.depths = [-1] * self.n self.parents = [[-1] * self.n for _ in range(self.logn)] self.__dfs(-1,root,0) self.__doubling() def __dfs(self,par,cur,dep): self.depths[cur]=dep self.parents[0][cur]=par for v in self.edges[cur]: if v!=par: self.__dfs(cur,v,dep+1) def __doubling(self): for k in range(self.logn - 1): for v in range(self.n): if self.parents[k][v] < 0: # 親がない continue self.parents[k+1][v]=self.parents[k][self.parents[k][v]] def get(self, u, v): # 深さを合わせる dd=self.depths[v]-self.depths[u] if dd<0: u, v = v, u dd*=-1 for k in range(self.logn): if dd&(1<<k): v = self.parents[k][v] if v == u: return v # にぶたん for k in reversed(range(self.logn)): pu,pv=self.parents[k][u],self.parents[k][v] if pu!=pv: u,v=pu,pv return self.parents[0][u] # input N = int(input()) edges = [[] for _ in range(N)] for _ in range(N-1): x,y=map(lambda x:int(x)-1,input().split()) edges[x].append(y) edges[y].append(x) lca = DoublingLCA(edges) Q = int(input()) for _ in range(Q): u,v=map(lambda x:int(x)-1,input().split()) print(lca.depths[u]+lca.depths[v]-2*lca.depths[lca.get(u,v)]+1) resolve()
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | moni0627 |
Language | PyPy3 (2.4.0) |
Score | 30 |
Code Size | 2193 Byte |
Status | TLE |
Exec Time | 2072 ms |
Memory | 159904 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 | 164 ms | 38384 KB |
subtask0_sample02.txt | AC | 165 ms | 38256 KB |
subtask0_sample03.txt | AC | 164 ms | 38256 KB |
subtask1_01.txt | AC | 862 ms | 149408 KB |
subtask1_02.txt | AC | 873 ms | 149408 KB |
subtask1_03.txt | AC | 166 ms | 38256 KB |
subtask1_04.txt | AC | 168 ms | 38256 KB |
subtask1_05.txt | AC | 211 ms | 41200 KB |
subtask1_06.txt | AC | 207 ms | 40176 KB |
subtask1_07.txt | AC | 734 ms | 76832 KB |
subtask1_08.txt | AC | 770 ms | 81440 KB |
subtask1_09.txt | AC | 774 ms | 85664 KB |
subtask1_10.txt | AC | 788 ms | 87584 KB |
subtask1_11.txt | AC | 800 ms | 90400 KB |
subtask1_12.txt | AC | 790 ms | 91168 KB |
subtask2_01.txt | AC | 1770 ms | 159904 KB |
subtask2_02.txt | AC | 1806 ms | 159776 KB |
subtask2_03.txt | AC | 1200 ms | 56152 KB |
subtask2_04.txt | AC | 1253 ms | 57432 KB |
subtask2_05.txt | AC | 1295 ms | 60120 KB |
subtask2_06.txt | AC | 1331 ms | 60344 KB |
subtask2_07.txt | AC | 1992 ms | 95008 KB |
subtask2_08.txt | AC | 1990 ms | 94240 KB |
subtask2_09.txt | AC | 1946 ms | 98132 KB |
subtask2_10.txt | AC | 1979 ms | 100384 KB |
subtask2_11.txt | TLE | 2068 ms | 101712 KB |
subtask2_12.txt | TLE | 2072 ms | 104096 KB |