結果
問題 | No.2563 色ごとのグループ |
ユーザー | ngng628 |
提出日時 | 2023-12-02 15:35:29 |
言語 | Crystal (1.11.2) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 2,167 bytes |
コンパイル時間 | 10,465 ms |
コンパイル使用メモリ | 292,652 KB |
実行使用メモリ | 78,676 KB |
最終ジャッジ日時 | 2023-12-02 15:35:49 |
合計ジャッジ時間 | 15,499 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 1 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 2 ms
6,548 KB |
testcase_05 | AC | 2 ms
6,548 KB |
testcase_06 | AC | 2 ms
6,548 KB |
testcase_07 | AC | 1 ms
6,548 KB |
testcase_08 | AC | 1 ms
6,548 KB |
testcase_09 | AC | 2 ms
6,548 KB |
testcase_10 | AC | 1 ms
6,548 KB |
testcase_11 | AC | 2 ms
6,548 KB |
testcase_12 | AC | 2 ms
6,548 KB |
testcase_13 | AC | 2 ms
6,548 KB |
testcase_14 | AC | 4 ms
6,548 KB |
testcase_15 | AC | 4 ms
6,548 KB |
testcase_16 | AC | 4 ms
6,548 KB |
testcase_17 | AC | 3 ms
6,548 KB |
testcase_18 | AC | 3 ms
6,548 KB |
testcase_19 | AC | 5 ms
6,548 KB |
testcase_20 | AC | 20 ms
8,832 KB |
testcase_21 | AC | 11 ms
6,548 KB |
testcase_22 | AC | 9 ms
6,548 KB |
testcase_23 | AC | 13 ms
6,548 KB |
testcase_24 | AC | 132 ms
31,260 KB |
testcase_25 | AC | 120 ms
39,596 KB |
testcase_26 | AC | 181 ms
51,076 KB |
testcase_27 | AC | 241 ms
62,468 KB |
testcase_28 | AC | 230 ms
56,112 KB |
testcase_29 | AC | 308 ms
73,620 KB |
testcase_30 | AC | 300 ms
73,620 KB |
testcase_31 | AC | 295 ms
73,620 KB |
testcase_32 | AC | 290 ms
73,620 KB |
testcase_33 | AC | 276 ms
78,676 KB |
testcase_34 | AC | 284 ms
78,456 KB |
testcase_35 | AC | 292 ms
78,456 KB |
testcase_36 | AC | 281 ms
78,676 KB |
testcase_37 | AC | 354 ms
78,676 KB |
ソースコード
main = -> { n, m = read_line.split.map &.to_i64 c = read_line.split.map &.to_i64.pred sizes = c.tally graph = Array.new(n) { |color| Array(Array(Int64)).new(sizes[color]? || 0) { [] of Int64 } } hash = Array.new(n) { Hash(Int64, Int32).new } m.times do u, v = read_line.split.map &.to_i64.pred if c[u] == c[v] color = c[u] hash[color][u] = hash[color].size unless hash[color].has_key?(u) hash[color][v] = hash[color].size unless hash[color].has_key?(v) u2 = hash[color][u] v2 = hash[color][v] graph[color][u2] << v2 graph[color][v2] << u2 end end ans = n.times.sum { |color| next 0_i64 if sizes.fetch(color, 0_i64) == 0 ut = NgLib::DisjointSet.new(sizes.fetch(color, 0_i64)) graph[color].each_with_index do |edges, u| edges.each do |v| ut.unite(u, v) end end ut.groups.size - 1 } puts ans } main.call module NgLib class DisjointSet @n : Int32 @parent_or_size : Array(Int32) def initialize @n = 0 @parent_or_size = Array(Int32).new end def initialize(size : Int) @n = size.to_i32 @parent_or_size = [-1] * size end def unite(a : Int, b : Int) : Int32 x = leader(a) y = leader(b) return x if x == y if -@parent_or_size[x] < -@parent_or_size[y] x, y = y, x end @parent_or_size[x] += @parent_or_size[y] @parent_or_size[y] = x x end def equiv?(a : Int, b : Int) : Bool leader(a) == leader(b) end def leader(a : Int) : Int32 return a.to_i32 if @parent_or_size[a] < 0 @parent_or_size[a] = leader(@parent_or_size[a]) @parent_or_size[a] end def size(a : Int) : Int32 -@parent_or_size[leader(a)] end def groups : Array(Array(Int32)) | Nil leader_buf = [0] * @n group_size = [0] * @n @n.times do |i| leader_buf[i] = leader(i) group_size[leader_buf[i]] += 1 end res = Array.new(@n){ [] of Int32 } @n.times do |i| res[leader_buf[i]] << i end res.delete([] of Int32) res end end end