結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-05 21:03:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 611 ms / 3,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 119 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 48,424 KB |
最終ジャッジ日時 | 2024-07-19 03:57:16 |
合計ジャッジ時間 | 7,984 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import defaultdictdef solve():N = int(input())E = defaultdict(list)for i in range(N - 1):x, y = map(int, input().split())E[x].append(y)E[y].append(x)R = [0] * (N + 1)L = [float('inf')] * (N + 1)visited = set()stack = [(1, 0)]s = set()while stack:v, r = stack.pop()visited.add(v)R[v] = rhasc = Falsefor c in E[v]:if c not in visited:stack.append((c, r + 1))hasc = Trueif not hasc:L[v] = 0s.add(v)def upd(x, d):if L[x] > d:L[x] = dreturn Truereturn Falsed = 1while s:ns = set()for i in s:for j in E[i]:if upd(j, d):ns.add(j)s = nsd += 1for i in range(1, N + 1):print(min(R[i], L[i]))if __name__ == '__main__':solve()