結果
問題 | No.1054 Union add query |
ユーザー | aaaaaaaaaa2230 |
提出日時 | 2022-04-06 23:28:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 809 ms / 2,000 ms |
コード長 | 1,481 bytes |
コンパイル時間 | 767 ms |
コンパイル使用メモリ | 87,216 KB |
実行使用メモリ | 191,544 KB |
最終ジャッジ日時 | 2023-08-18 15:01:24 |
合計ジャッジ時間 | 7,519 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
71,580 KB |
testcase_01 | AC | 59 ms
71,364 KB |
testcase_02 | AC | 60 ms
71,488 KB |
testcase_03 | AC | 809 ms
155,276 KB |
testcase_04 | AC | 794 ms
191,544 KB |
testcase_05 | AC | 635 ms
143,584 KB |
testcase_06 | AC | 495 ms
161,104 KB |
testcase_07 | AC | 473 ms
161,532 KB |
testcase_08 | AC | 518 ms
161,448 KB |
testcase_09 | AC | 519 ms
179,260 KB |
testcase_10 | AC | 432 ms
177,716 KB |
ソースコード
class Unionfind: def __init__(self,n): self.uf = [-1]*n self.p = [[i] for i in range(n)] self.count = [0]*n def find(self,x): if self.uf[x] < 0: return x else: self.uf[x] = self.find(self.uf[x]) return self.uf[x] def same(self,x,y): return self.find(x) == self.find(y) def union(self,x,y): x = self.find(x) y = self.find(y) if x == y: return False if self.uf[x] > self.uf[y]: x,y = y,x cx = self.count[x] cy = self.count[y] for i in self.p[y]: if i != y: self.count[i] += cy-cx else: self.count[i] += -cx self.p[x].append(i) self.p[y] = [] self.uf[x] += self.uf[y] self.uf[y] = x return True def size(self,x): x = self.find(x) return -self.uf[x] def add(self,a,b): self.count[self.find(a)] += b def solve(self,a): num = self.count[a] if self.find(a) != a: num += self.count[self.find(a)] return num n,q = map(int,input().split()) uf = Unionfind(n) Q = [list(map(int,input().split())) for i in range(q)] for t,a,b in Q: if t == 1: a,b = a-1,b-1 if uf.same(a,b): continue uf.union(a,b) elif t == 2: uf.add(a-1,b) else: print(uf.solve(a-1))