結果
問題 | No.1054 Union add query |
ユーザー | brthyyjp |
提出日時 | 2020-05-26 04:27:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 886 ms / 2,000 ms |
コード長 | 1,091 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 233,080 KB |
最終ジャッジ日時 | 2024-04-21 04:08:32 |
合計ジャッジ時間 | 5,685 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
52,224 KB |
testcase_01 | AC | 38 ms
52,224 KB |
testcase_02 | AC | 39 ms
51,712 KB |
testcase_03 | AC | 584 ms
123,112 KB |
testcase_04 | AC | 886 ms
233,080 KB |
testcase_05 | AC | 425 ms
100,724 KB |
testcase_06 | AC | 371 ms
163,136 KB |
testcase_07 | AC | 331 ms
162,960 KB |
testcase_08 | AC | 351 ms
162,408 KB |
testcase_09 | AC | 430 ms
224,896 KB |
testcase_10 | AC | 319 ms
223,360 KB |
ソースコード
def Find(x, par): if par[x] < 0: return x else: par[x] = Find(par[x], par) return par[x] def Unite(x, y, par, size, plus, child): x = Find(x, par) y = Find(y, par) if x != y: if size[x] < size[y]: x, y = y, x size[x] += size[y] par[y] = x sub = plus[y]-plus[x] plus[y] = 0 for k in child[y]: child[x].add(k) plus[k] += sub child[y] = set() def Same(x, y, par): return Find(x, par) == Find(y, par) def Size(x, par, size): return size[Find(x, par)] import sys input = sys.stdin.buffer.readline n, q = map(int, input().split()) par = [-1]*n size = [1]*n child = [{i} for i in range(n)] plus = [0]*n for i in range(q): t, a, b = map(int, input().split()) if t == 1: a, b = a-1, b-1 Unite(a, b, par, size, plus, child) elif t == 2: a -= 1 plus[Find(a, par)] += b else: a -= 1 if par[a] == -1: print(plus[a]) else: print(plus[a]+plus[Find(a, par)])