結果
問題 | No.1054 Union add query |
ユーザー | siman |
提出日時 | 2022-04-06 05:51:36 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 1,304 ms / 2,000 ms |
コード長 | 994 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 11,200 KB |
実行使用メモリ | 27,400 KB |
最終ジャッジ日時 | 2023-08-18 11:53:41 |
合計ジャッジ時間 | 13,261 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 80 ms
15,028 KB |
testcase_01 | AC | 79 ms
15,336 KB |
testcase_02 | AC | 80 ms
15,264 KB |
testcase_03 | AC | 1,234 ms
17,868 KB |
testcase_04 | AC | 1,304 ms
27,400 KB |
testcase_05 | AC | 1,215 ms
16,748 KB |
testcase_06 | AC | 1,177 ms
20,112 KB |
testcase_07 | AC | 1,116 ms
20,280 KB |
testcase_08 | AC | 1,092 ms
20,084 KB |
testcase_09 | AC | 1,248 ms
27,116 KB |
testcase_10 | AC | 912 ms
27,196 KB |
コンパイルメッセージ
Syntax OK
ソースコード
class UnionFind def initialize(n) @size = Array.new(n, 1) @b = Array.new(n, 0) @parent = [] (0..n).each do |i| @parent[i] = i end end def find(x) if @parent[x] == x x else find(@parent[x]) end end def add(x, v) root = find(x) @b[root] += v end def get(x) if @parent[x] == x @b[x] else @b[x] + get(@parent[x]) end end def unite(x, y) x = find(x) y = find(y) return if x == y if @size[x] < @size[y] @parent[x] = y @size[y] += @size[x] @b[x] -= @b[y] else @parent[y] = x @size[x] += @size[y] @b[y] -= @b[x] end end def same?(x, y) find(x) == find(y) end def size(x) @size[find(x)] end end N, Q = gets.split.map(&:to_i) uf = UnionFind.new(N + 1) A = Hash.new(0) Q.times do t, a, b = gets.split.map(&:to_i) case t when 1 uf.unite(a, b) when 2 uf.add(a, b) when 3 puts uf.get(a) end end