結果

問題 No.1420 国勢調査 (Easy)
ユーザー qib
提出日時 2023-01-23 00:32:24
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,311 bytes
コンパイル時間 744 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 857,344 KB
最終ジャッジ日時 2024-06-25 01:44:51
合計ジャッジ時間 5,419 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
sys.setrecursionlimit(10 ** 6)
class WeightedUnionFind:
def __init__(self, n):
self.node = [-1 for _ in range(n)]
self.value = [0 for _ in range(n)]
def root(self, x):
if self.node[x] < 0:
return x
else:
r = self.root(self.node[x])
self.value[x] ^= self.value[self.node[x]]
self.node[x] = r
return r
def size(self, x):
x = self.root(x)
return (- self.node[x])
def is_same(self, x, y):
return self.root(x) == self.root(y)
def weight(self, x):
self.root(x)
return self.value[x]
def diff(self, x, y):
return self.weight(y) ^ self.weight(x)
def unite(self, x, y, w):
w ^= self.weight(x)
w ^= self.weight(y)
rx = self.root(x)
ry = self.root(y)
if rx == ry:
return
dx = self.node[x]
dy = self.node[y]
if dx <= dy:
self.node[ry] = rx
self.node[rx] += dy
self.value[ry] = w
else:
self.node[rx] = ry
self.node[ry] += dx
self.value[rx] = w
n, m = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
y = int(input())
if not wuf.is_same(a, b):
wuf.unite(a, b, y)
elif wuf.diff(a, b) != y:
print("-1")
exit()
for v in range(n):
print(wuf.weight(v))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0