結果

問題 No.1420 国勢調査 (Easy)
ユーザー brthyyjpbrthyyjp
提出日時 2021-03-05 22:58:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 363 ms / 2,000 ms
コード長 1,555 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 85,828 KB
最終ジャッジ日時 2024-04-16 10:58:36
合計ジャッジ時間 8,287 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,224 KB
testcase_01 AC 43 ms
52,096 KB
testcase_02 AC 220 ms
77,044 KB
testcase_03 AC 223 ms
78,164 KB
testcase_04 AC 209 ms
77,720 KB
testcase_05 AC 213 ms
78,320 KB
testcase_06 AC 213 ms
77,836 KB
testcase_07 AC 184 ms
78,076 KB
testcase_08 AC 191 ms
77,756 KB
testcase_09 AC 177 ms
77,440 KB
testcase_10 AC 195 ms
77,656 KB
testcase_11 AC 182 ms
78,020 KB
testcase_12 AC 70 ms
71,296 KB
testcase_13 AC 118 ms
82,304 KB
testcase_14 AC 91 ms
78,208 KB
testcase_15 AC 118 ms
82,304 KB
testcase_16 AC 117 ms
82,176 KB
testcase_17 AC 118 ms
82,176 KB
testcase_18 AC 116 ms
82,176 KB
testcase_19 AC 117 ms
82,176 KB
testcase_20 AC 116 ms
82,176 KB
testcase_21 AC 112 ms
82,176 KB
testcase_22 AC 340 ms
85,280 KB
testcase_23 AC 363 ms
85,656 KB
testcase_24 AC 343 ms
85,448 KB
testcase_25 AC 350 ms
85,828 KB
testcase_26 AC 336 ms
85,200 KB
testcase_27 AC 179 ms
79,488 KB
testcase_28 AC 174 ms
79,104 KB
testcase_29 AC 126 ms
78,848 KB
testcase_30 AC 185 ms
79,872 KB
testcase_31 AC 171 ms
78,464 KB
権限があれば一括ダウンロードができます

ソースコード

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