結果
問題 | No.1817 Reversed Edges |
ユーザー |
![]() |
提出日時 | 2022-01-22 09:17:37 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 721 ms / 2,000 ms |
コード長 | 865 bytes |
コンパイル時間 | 119 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 32,652 KB |
最終ジャッジ日時 | 2024-11-27 02:38:07 |
合計ジャッジ時間 | 13,502 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
n = int(input())graph = [[] for _ in range(n)]for _ in range(n - 1):a, b = map(int, input().split())a -= 1b -= 1graph[a].append(b)graph[b].append(a)# 始めに頂点位置のスコアを求める。score = 0q = [(0, -1)] # now, parentwhile q:now, par = q.pop()if par > now:score += 1for nxt in graph[now]:if nxt != par:q.append((nxt, now))# 今いる頂点nowから隣接する頂点nxtに移動してnow<nxtならスコア+1, now>nxtならスコア-1するans = [0] * nans[0] = scoreq = [(0, -1)] # now, parentwhile q:now, par = q.pop()for nxt in graph[now]:if nxt != par:if nxt > now:ans[nxt] = ans[now] + 1else:ans[nxt] = ans[now] - 1q.append((nxt, now))for a in ans:print(a)