結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
👑 ![]() |
提出日時 | 2021-03-05 22:18:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,052 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 121,072 KB |
最終ジャッジ日時 | 2024-10-07 02:33:40 |
合計ジャッジ時間 | 26,212 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 TLE * 3 |
ソースコード
"""桁ごとに求められる1箇所決め打てば、後は連鎖的に決まる桁ごとにdfsして、矛盾なければおk"""import sysfrom sys import stdinfrom collections import dequeN,M = map(int,stdin.readline().split())lis = [ [] for i in range(N) ]for i in range(M):A,B = map(int,stdin.readline().split())A -= 1B -= 1Y = int(stdin.readline())lis[A].append((B,Y))lis[B].append((A,Y))ans = [0] * Nfor dig in range(30):nd = 2**digable = [True] * Nfor st in range(N):if able[st]:q = deque([st])able[st] = Falsewhile q:v = q.popleft()for nex,Y in lis[v]:if able[nex]:able[nex] = Falseans[nex] |= (Y ^ ans[v]) & ndq.append(nex)elif ans[nex] & nd != (Y ^ ans[v]) & nd:print (-1)sys.exit()print ("\n".join(map(str,ans)))