結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-06-20 03:26:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,968 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 82,048 KB |
最終ジャッジ日時 | 2024-06-22 22:24:32 |
合計ジャッジ時間 | 10,206 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 12 WA * 18 |
ソースコード
class PotentialUnionFind_general:def __init__(self, n, add, inv, e_M):self.parent = [-1]*n #親ノード or sizeself.wt = [0]*n #親ノードを基準としたポテンシャルself.add = add #足し算self.inv = inv #逆元self.e_M = e_M #単位元def root(self, x): #root(x): xの根ノードを返す.while self.parent[x] >= 0:x = self.parent[x]return xdef weight(self, x): # p(x) - p(root)c = self.e_Mwhile self.parent[x] >= 0:c = self.add(self.wt[x], c)x = self.parent[x]return cdef merge(self, x, y, dxy): #ポテンシャル差p(y)-p(x)=dxyでxとyの組をまとめるdxy = self.add(self.add(self.weight(x),dxy), inv(self.weight(y))) #dxyを置き換えx,y = self.root(x), self.root(y)if x == y: return Falseif self.parent[x] > self.parent[y]: #rxの要素数が大きいようにx,y,dxy = y,x,inv(dxy)self.parent[x] += self.parent[y] #xの要素数を更新self.parent[y] = x #ryをrxにつなぐself.wt[y] = dxy #ryの相対ポテンシャルを更新return Truedef issame(self, x, y): #same(x,y): xとyが同じ組ならTruereturn self.root(x) == self.root(y)def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返すreturn add(inv(self.weight(x)), self.weight(y))def size(self,x): #size(x): xのいるグループの要素数を返すreturn self.gsize[self.root(x)]import sysreadline = sys.stdin.readlinen,m = map(int,readline().split())add = lambda x,y: x^yinv = lambda x: xUF = PotentialUnionFind_general(n+1,add,inv,0)for _ in range(m):l,r = map(int,readline().split())y = int(readline())if not UF.merge(l,r,y):if UF.diff(l,r) != y:print(-1)exit()print(UF.wt[1:], sep="\n")