結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2023-05-07 12:45:34 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,549 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 81,688 KB |
最終ジャッジ日時 | 2024-11-24 13:08:39 |
合計ジャッジ時間 | 11,522 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 WA * 10 RE * 10 |
ソースコード
import sysinput = sys.stdin.readlineclass UnionFind(object):def __init__(self, n=1):self.par = [i for i in range(n)]self.rank = [0 for _ in range(n)]self.size = [1 for _ in range(n)]self.diff_weight = [0 for _ in range(n)]self.flag = 1def find(self, x):if self.par[x] == x:return xelse:root = self.find(self.par[x])self.diff_weight[x] ^= self.diff_weight[self.par[x]]self.par[x] = rootreturn self.par[x]def union(self, x, y, w):rx = self.find(x)ry = self.find(y)w ^= self.diff_weight[y]^self.diff_weight[x]if rx != ry:if self.rank[rx] < self.rank[ry]:rx, ry = ry, rxif self.rank[rx] == self.rank[ry]:self.rank[rx] += 1self.par[ry] = rxself.size[rx] += self.size[ry]self.diff_weight[ry] = welse:if w:self.flag = 0def is_same(self, x, y):return self.find(x) == self.find(y)def get_size(self, x):x = self.find(x)return self.size[x]def diff(self, x, y):return self.diff_weight[y]^self.diff_weight[x]N, M = map(int, input().split())U = UnionFind(N)for i in range(N):A, B = map(int, input().split())A, B = A - 1, B - 1Y = int(input())U.union(A, B, Y)if U.flag:for i in range(N):print(U.diff(U.find(i), i))else:print(-1)