結果
問題 | No.277 根掘り葉掘り |
ユーザー | convexineq |
提出日時 | 2020-12-26 17:45:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 336 ms / 3,000 ms |
コード長 | 681 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 81,684 KB |
実行使用メモリ | 115,636 KB |
最終ジャッジ日時 | 2023-10-25 01:18:03 |
合計ジャッジ時間 | 5,156 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
55,360 KB |
testcase_01 | AC | 41 ms
55,360 KB |
testcase_02 | AC | 42 ms
55,360 KB |
testcase_03 | AC | 44 ms
55,360 KB |
testcase_04 | AC | 44 ms
55,360 KB |
testcase_05 | AC | 44 ms
55,360 KB |
testcase_06 | AC | 44 ms
55,360 KB |
testcase_07 | AC | 44 ms
55,360 KB |
testcase_08 | AC | 42 ms
55,360 KB |
testcase_09 | AC | 274 ms
105,868 KB |
testcase_10 | AC | 267 ms
115,636 KB |
testcase_11 | AC | 315 ms
100,832 KB |
testcase_12 | AC | 299 ms
105,868 KB |
testcase_13 | AC | 336 ms
101,256 KB |
testcase_14 | AC | 311 ms
102,096 KB |
testcase_15 | AC | 310 ms
100,856 KB |
testcase_16 | AC | 318 ms
101,512 KB |
testcase_17 | AC | 312 ms
102,008 KB |
testcase_18 | AC | 313 ms
101,608 KB |
testcase_19 | AC | 331 ms
100,932 KB |
ソースコード
n = int(input()) g = [[] for _ in range(n)] for i in range(n-1): a,b = [int(i) for i in input().split()] g[a-1].append(b-1) g[b-1].append(a-1) order = [] st = [0] parent = [-1]*n L = [0]*n while st: v = st.pop() order.append(v) for c in g[v]: if c != parent[v]: st.append(c) parent[c] = v L[c] = L[v]+1 from collections import deque q = deque() R = [-1]*n for i in range(1,n): if len(g[i]) == 1: q.append(i) R[i] = 0 while q: v = q.popleft() for c in g[v]: if R[c] == -1: R[c] = R[v]+1 q.append(c) print(*(min(li,ri) for li,ri in zip(L,R)),sep="\n")