結果
問題 | No.1054 Union add query |
ユーザー | Shinya Fujita |
提出日時 | 2024-10-07 23:34:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,054 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 90,528 KB |
最終ジャッジ日時 | 2024-10-07 23:34:39 |
合計ジャッジ時間 | 9,068 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,004 KB |
testcase_01 | AC | 36 ms
52,152 KB |
testcase_02 | AC | 35 ms
53,368 KB |
testcase_03 | AC | 1,054 ms
81,676 KB |
testcase_04 | AC | 1,018 ms
90,528 KB |
testcase_05 | AC | 1,007 ms
80,552 KB |
testcase_06 | AC | 673 ms
81,800 KB |
testcase_07 | AC | 639 ms
81,620 KB |
testcase_08 | AC | 557 ms
81,816 KB |
testcase_09 | AC | 924 ms
88,824 KB |
testcase_10 | AC | 286 ms
87,996 KB |
ソースコード
class UnionFind: def __init__(self, n=1): self.parent = [i for i in range(n)] self.rank = [0] * n self.value = [0] * n def find(self, x): if self.parent[x] == x: return x, 0 else: p, v = self.find(self.parent[x]) self.parent[x] = p self.value[x] += v return self.parent[x], self.value[x] def union(self, x, y): x, _ = self.find(x) y, _ = self.find(y) if x != y: if self.rank[x] < self.rank[y]: x, y = y, x if self.rank[x] == self.rank[y]: self.rank[x] += 1 self.parent[y] = x self.value[y] -= self.value[x] def is_same(self, x, y): return self.find(x)[0] == self.find(y)[0] def add(self, x, v): p, _ = self.find(x) self.value[p] += v def get_value(self, x): p, _ = self.find(x) return self.value[x] + self.value[p]*(p!=x) N, Q = map(int, input().split()) uf = UnionFind(N) for _ in range(Q): t, a, b = map(int, input().split()) a -= 1 if t == 1: b -= 1 uf.union(a, b) elif t == 2: uf.add(a, b) else: v = uf.get_value(a) print(v)