Submission #4653140
Source Code Expand
N = int(input()) XY = [list(map(int,input().split())) for _ in range(1,N)] Q = int(input()) AB = [list(map(int,input().split())) for _ in range(Q)] LCA = list(range(N+1)) import sys sys.getrecursionlimit(10**5) def getV(lca,inte):#inteが経由する頂点を全て返す。ただしLCAは1を基準とする。 #全ての頂点が辺でつながれない、または閉路が存在する場合兵庫県警に逮捕される if inte == 1: return [1] elif lca[inte] == 1: return [1,inte] else: return getV(lca,lca[inte])+[inte] def getD(lca,int1,int2):#int1 < int2 である方が望ましい L1 = getV(lca,int1) L2 = getV(lca,int2) length1 = -1 length2 = 0 for l in L1[::-1]: length1 += 1 if L2.__contains__(l): length2 = len(L2[L2.index(l):])-1 break return length1+length2 for x,y in XY: LCA[max(x,y)] = min(x,y) for a,b in AB: print(getD(LCA,min(a,b),max(a,b))+1)
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | BARISU |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 1110 Byte |
Status | RE |
Exec Time | 678 ms |
Memory | 55724 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 | 17 ms | 3064 KB |
subtask0_sample02.txt | RE | 17 ms | 3064 KB |
subtask0_sample03.txt | RE | 17 ms | 3064 KB |
subtask1_01.txt | RE | 323 ms | 31252 KB |
subtask1_02.txt | RE | 319 ms | 31252 KB |
subtask1_03.txt | RE | 17 ms | 3064 KB |
subtask1_04.txt | RE | 17 ms | 3064 KB |
subtask1_05.txt | RE | 20 ms | 3188 KB |
subtask1_06.txt | RE | 20 ms | 3188 KB |
subtask1_07.txt | RE | 307 ms | 31340 KB |
subtask1_08.txt | RE | 328 ms | 31348 KB |
subtask1_09.txt | RE | 331 ms | 31356 KB |
subtask1_10.txt | RE | 327 ms | 31360 KB |
subtask1_11.txt | RE | 321 ms | 31324 KB |
subtask1_12.txt | RE | 312 ms | 31340 KB |
subtask2_01.txt | RE | 631 ms | 52556 KB |
subtask2_02.txt | RE | 626 ms | 54840 KB |
subtask2_03.txt | RE | 295 ms | 20980 KB |
subtask2_04.txt | RE | 302 ms | 20980 KB |
subtask2_05.txt | RE | 300 ms | 26004 KB |
subtask2_06.txt | RE | 328 ms | 26012 KB |
subtask2_07.txt | RE | 649 ms | 55704 KB |
subtask2_08.txt | RE | 654 ms | 55624 KB |
subtask2_09.txt | RE | 632 ms | 55612 KB |
subtask2_10.txt | RE | 678 ms | 55712 KB |
subtask2_11.txt | RE | 623 ms | 55620 KB |
subtask2_12.txt | RE | 631 ms | 55724 KB |