Submission #4653159
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)) def getV(lca,inte):#inteが経由する頂点を全て返す。ただしLCAは1を基準とする。 #全ての頂点が辺でつながれない、または閉路が存在する場合兵庫県警に逮捕される ans = [] while True: if lca[inte] == 1: return [1,inte]+ans break elif inte == 1: return [1]+ans else: ans = [inte] + ans inte =lca[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 | 1114 Byte |
Status | TLE |
Exec Time | 2107 ms |
Memory | 56304 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 | 17 ms | 3064 KB |
subtask0_sample02.txt | AC | 17 ms | 3064 KB |
subtask0_sample03.txt | AC | 17 ms | 3064 KB |
subtask1_01.txt | TLE | 2105 ms | 31292 KB |
subtask1_02.txt | TLE | 2105 ms | 31292 KB |
subtask1_03.txt | TLE | 2104 ms | 3784 KB |
subtask1_04.txt | TLE | 2104 ms | 3792 KB |
subtask1_05.txt | TLE | 2103 ms | 3976 KB |
subtask1_06.txt | TLE | 2103 ms | 3968 KB |
subtask1_07.txt | TLE | 2106 ms | 31976 KB |
subtask1_08.txt | TLE | 2106 ms | 31984 KB |
subtask1_09.txt | TLE | 2106 ms | 31984 KB |
subtask1_10.txt | TLE | 2106 ms | 31980 KB |
subtask1_11.txt | TLE | 2106 ms | 31984 KB |
subtask1_12.txt | TLE | 2105 ms | 33892 KB |
subtask2_01.txt | TLE | 2107 ms | 52468 KB |
subtask2_02.txt | TLE | 2107 ms | 54880 KB |
subtask2_03.txt | TLE | 2105 ms | 21708 KB |
subtask2_04.txt | TLE | 2105 ms | 21716 KB |
subtask2_05.txt | TLE | 2105 ms | 26684 KB |
subtask2_06.txt | TLE | 2105 ms | 26696 KB |
subtask2_07.txt | TLE | 2107 ms | 56300 KB |
subtask2_08.txt | TLE | 2107 ms | 56296 KB |
subtask2_09.txt | TLE | 2107 ms | 56292 KB |
subtask2_10.txt | TLE | 2107 ms | 56304 KB |
subtask2_11.txt | TLE | 2107 ms | 56292 KB |
subtask2_12.txt | TLE | 2107 ms | 56296 KB |