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
RE × 3
RE × 12
RE × 27
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