結果

問題 No.1420 国勢調査 (Easy)
コンテスト
ユーザー brthyyjp
提出日時 2021-03-05 22:58:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 345 ms / 2,000 ms
コード長 1,555 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 85,656 KB
最終ジャッジ日時 2024-10-07 04:22:10
合計ジャッジ時間 8,370 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Find(x, par, diff_weight):
    if par[x] < 0:
        return x
    else:
        px = Find(par[x], par, diff_weight)
        diff_weight[x] ^= diff_weight[par[x]]
        par[x] = px
        return px

def Unite(x, y, par, rank, diff_weight, w):
    w ^= diff_weight[x] ^ diff_weight[y]
    x = Find(x, par, diff_weight)
    y = Find(y, par, diff_weight)

    if x != y:
        if rank[x] < rank[y]:
            x, y =  y, x
        if rank[x] == rank[y]:
            rank[x] += 1
        par[x] += par[y]
        par[y] = x
        diff_weight[y] = w

def Same(x, y, par, diff_weight):
    return Find(x, par,diff_weight) == Find(y, par, diff_weight)

def Size(x, par, diff_weight):
    return -par[Find(x, par, diff_weight)]

def Weight(x, par, diff_weight):
    Find(x, par, diff_weight)
    return diff_weight[x]

def Diff(x, y, par, diff_weight):
    return Weight(y, par, diff_weight) ^ Weight(x, par, diff_weight)

import sys
import io, os
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
par = [-1]*n
rank = [0]*n
diff_weight = [0]*n

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    y = int(input())
    if not Same(a, b, par, diff_weight):
        Unite(a, b, par, rank, diff_weight, y)
    else:
        if y != Diff(a, b, par, diff_weight):
            print(-1)
            exit()
    #print(i, diff_weight, par)
#print(diff_weight)
X = [0]*n
for i in range(n):
    if par[i] < 0:
        continue
    else:
        X[i] = X[Find(i, par, diff_weight)]^diff_weight[i]
print(*X, sep='\n')
0