結果
問題 |
No.1817 Reversed Edges
|
ユーザー |
|
提出日時 | 2023-08-12 15:28:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 357 ms / 2,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 96,484 KB |
最終ジャッジ日時 | 2024-11-20 02:38:25 |
合計ジャッジ時間 | 8,270 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
import collections N = int(input()) lsg = [[] for i in range(N)] for i in range(N-1): a,b = map(int,input().split()) a -= 1 b -= 1 lsg[a].append(b) lsg[b].append(a) used = [False]*(N) d = collections.deque([0]) ans0 = 0 while d: n = d.pop() if used[n]: continue used[n] = True for g in lsg[n]: if used[g]: continue if n > g: ans0 += 1 d.append(g) lsans = [0]*(N) lsans[0] = ans0 used = [False]*(N) d = collections.deque([0]) while d: n = d.pop() if used[n]: continue used[n] = True for g in lsg[n]: if used[g]: continue if n > g: lsans[g] = lsans[n]-1 else: lsans[g] = lsans[n]+1 d.append(g) print(*lsans,sep='\n')