Submission #33651113

Source Code Expand

import sys
import re
from collections import deque

sys.setrecursionlimit(100000)
deb = 0
n = int(input())
paths = [[] for i  in range(n+1)]
for i in range(0,n-1) :
    a , b=  map(int, input().split()) 
    paths[a].append(b)
    paths[b].append(a)

#print(paths)
cons = [0 for i in range(n+1)]
dists = [0 for i in range(n+1)]

def doDfs(s):
    dist = 0 
    Q = deque()
    Q.append([s,dist])
    while Q :
        x = Q[-1][0]
        dist = Q[-1][-1]
        Q.pop()
        if cons[x]>0 : continue 
        else :
            cons[x]=1
            dists[x]=dist
            for y in paths[x] :
                Q.append([y,dist+1])

doDfs(1)
s = dists.index(max(dists))
cons = [0 for i in range(n+1)]
dists = [0 for i in range(n+1)]
doDfs(s)

#for i in range(1,n+1) :
#    if len(paths[i]) == 1 and cons[i] == 0 :
#        doDfs(i)
#print(dists)
print (max(dists)+1)

Submission Info

Submission Time
Task 003 - Longest Circular Road（★4）
User ay24h
Language PyPy3 (7.3.0)
Score 4
Code Size 913 Byte
Status AC
Exec Time 317 ms
Memory 117176 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 4 / 4
Status
AC × 4
AC × 26
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt
Case Name Status Exec Time Memory
sample_01.txt AC 121 ms 70164 KiB
sample_02.txt AC 65 ms 70140 KiB
sample_03.txt AC 70 ms 70248 KiB
sample_04.txt AC 67 ms 70384 KiB
subtask_1_01.txt AC 69 ms 70848 KiB
subtask_1_02.txt AC 68 ms 71036 KiB
subtask_1_03.txt AC 74 ms 73608 KiB
subtask_1_04.txt AC 295 ms 97192 KiB
subtask_1_05.txt AC 248 ms 93796 KiB
subtask_1_06.txt AC 259 ms 96152 KiB
subtask_1_07.txt AC 76 ms 74244 KiB
subtask_1_08.txt AC 128 ms 78336 KiB
subtask_1_09.txt AC 121 ms 77696 KiB
subtask_1_10.txt AC 87 ms 74620 KiB
subtask_1_11.txt AC 66 ms 70284 KiB
subtask_1_12.txt AC 282 ms 98620 KiB
subtask_1_13.txt AC 160 ms 82460 KiB
subtask_1_14.txt AC 67 ms 70508 KiB
subtask_1_15.txt AC 128 ms 78380 KiB
subtask_1_16.txt AC 311 ms 102568 KiB
subtask_1_17.txt AC 314 ms 102740 KiB
subtask_1_18.txt AC 317 ms 102524 KiB
subtask_1_19.txt AC 314 ms 102700 KiB
subtask_1_20.txt AC 316 ms 102468 KiB
subtask_1_21.txt AC 257 ms 108552 KiB
subtask_1_22.txt AC 261 ms 117176 KiB