結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-03-05 23:52:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 601 ms / 2,000 ms |
コード長 | 1,166 bytes |
コンパイル時間 | 1,207 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 124,092 KB |
最終ジャッジ日時 | 2024-10-07 06:03:54 |
合計ジャッジ時間 | 13,950 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from collections import defaultdictn, m = map(int, input().split())graph = [[] for _ in range(n)]memo = defaultdict(lambda: defaultdict(lambda: -1))for _ in range(m):a, b = map(int, input().split())y = int(input())a, b = a - 1, b - 1graph[a].append(b)graph[b].append(a)if a > b:b, a = a, bif memo[a][b] >= 0:if memo[a][b] == y:continueelse:print(-1)exit()memo[a][b] = yused = [0] * nans = [-1] * nfor i in range(n):if not used[i]:stack = [i]used[i] = 1ans[i] = 0while stack:v = stack.pop()now = ans[v]for u in graph[v]:if u < v:temp = memo[u][v]else:temp = memo[v][u]if used[u]:if ans[u] ^ ans[v] == temp:continueelse:print(-1)exit()used[u] = 1ans[u] = temp ^ ans[v]stack.append(u)for a in ans:print(a)