結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
|
提出日時 | 2021-03-15 10:21:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 404 ms / 2,000 ms |
コード長 | 1,056 bytes |
コンパイル時間 | 621 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 133,268 KB |
最終ジャッジ日時 | 2024-11-06 23:19:48 |
合計ジャッジ時間 | 10,449 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import sysinput=sys.stdin.readlinedef main1(n,m,aby):g=[[] for _ in range(n)]for a,b,y in aby:a,b=a-1,b-1g[a].append([b,y])g[b].append([a,y])x=[0]*nflg=Truemi=set(range(n))seen=[-1]*nwhile mi:v0=mi.pop()grp=set()flg=Trueseen[v0]=0todo=[v0]grp={v0}while todo:v=todo.pop()mi.discard(v)grp.add(v)for nv,y in g[v]:if seen[nv]==-1:seen[nv]=seen[v]^ytodo.append(nv)elif seen[nv]==seen[v]^y:continueelse:flg=Falsebreakif not flg:breakif not flg:return [-1]for v in grp:if seen[v]>0:x[v]+=seen[v]return xdef chk(n,aby,x):for a,b,y in aby:a,b=a-1,b-1if x[a]^x[b]==y:passelse:return Falsereturn Trueif __name__=='__main__':n,m=map(int,input().split())aby=[]for _ in range(m):a,b=map(int,input().split())y=int(input())aby.append([a,b,y])ret1=main1(n,m,aby)print(*ret1,sep='\n')