結果
問題 | No.2563 色ごとのグループ |
ユーザー | InTheBloom |
提出日時 | 2023-12-02 15:16:30 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 605 ms / 2,000 ms |
コード長 | 2,603 bytes |
コンパイル時間 | 1,954 ms |
コンパイル使用メモリ | 164,608 KB |
実行使用メモリ | 112,304 KB |
最終ジャッジ日時 | 2023-12-02 15:16:40 |
合計ジャッジ時間 | 9,720 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 1 ms
6,676 KB |
testcase_04 | AC | 1 ms
6,676 KB |
testcase_05 | AC | 1 ms
6,676 KB |
testcase_06 | AC | 1 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 3 ms
6,676 KB |
testcase_10 | AC | 3 ms
6,676 KB |
testcase_11 | AC | 1 ms
6,676 KB |
testcase_12 | AC | 1 ms
6,676 KB |
testcase_13 | AC | 1 ms
6,676 KB |
testcase_14 | AC | 3 ms
6,676 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 4 ms
6,676 KB |
testcase_17 | AC | 4 ms
6,676 KB |
testcase_18 | AC | 3 ms
6,676 KB |
testcase_19 | AC | 7 ms
6,676 KB |
testcase_20 | AC | 23 ms
12,112 KB |
testcase_21 | AC | 13 ms
9,592 KB |
testcase_22 | AC | 11 ms
9,596 KB |
testcase_23 | AC | 17 ms
11,644 KB |
testcase_24 | AC | 221 ms
61,172 KB |
testcase_25 | AC | 189 ms
53,716 KB |
testcase_26 | AC | 342 ms
63,600 KB |
testcase_27 | AC | 348 ms
94,144 KB |
testcase_28 | AC | 385 ms
79,748 KB |
testcase_29 | AC | 559 ms
111,152 KB |
testcase_30 | AC | 605 ms
111,180 KB |
testcase_31 | AC | 563 ms
112,188 KB |
testcase_32 | AC | 596 ms
112,304 KB |
testcase_33 | AC | 470 ms
56,932 KB |
testcase_34 | AC | 462 ms
57,100 KB |
testcase_35 | AC | 447 ms
57,100 KB |
testcase_36 | AC | 460 ms
56,932 KB |
testcase_37 | AC | 455 ms
56,932 KB |
ソースコード
import std; void main () { /* 色ごとの全域木をつくるかんじで 辞書型UFでずるする */ int N, M; readln.read(N, M); int[] C = readln.split.to!(int[]); alias UFarr = UnionFind_Dictionary!(int); UFarr[int] UF; foreach (c; C) UF[c] = UnionFind_Any!(int); // 登録 foreach (i, c; C) UF[c].addElement(cast(int) i); foreach (i; 0..M) { int u, v; readln.read(u, v); u--, v--; if (C[u] == C[v]) { UF[C[u]].unite(u, v); } } int ans = 0; foreach (U; UF) { ans += U.countGroups-1; } writeln(ans); } void read (T...) (string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } class UnionFind_Dictionary (T) { private: T[T] parent; int[T] size; T root (T x) { if (x !in parent) { addElement(x); return x; } if (parent[x] == x) return x; return parent[x] = root(parent[x]); } bool same (T x, T y) { return root(x) == root(y); } void unite (T x, T y) { addElement(x), addElement(y); T larger, smaller; if (GroupSize(x) <= GroupSize(y)) { larger = root(y); smaller = root(x); } else { larger = root(x); smaller = root(y); } if (larger == smaller) return; parent[smaller] = larger; size[larger] += size[smaller]; } int countGroups () { int res = 0; foreach (key, val; parent) { if (root(key) == key) res++; } return res; } bool addElement (T x) { if (x in parent) return false; parent[x] = x; size[x] = 1; return true; } int GroupSize (T x) { addElement(x); return size[root(x)]; } T[][] enumGroups (T x) { T[][T] mp; T[][] res; foreach (key, val; parent) { mp[root(key)] ~= key; } foreach (val; mp) { res ~= val; } return res; } void reset () { parent.clear; size.clear; } } auto UnionFind_Any (T) () { return new UnionFind_Dictionary!(T)(); } import std.range.primitives : isInputRange; auto UnionFind_Any (T, E) (E range) if (isInputRange!(E) || is(T == S[], S) || is(T == S[n], S, size_t n)) { auto res = new UnionFind_Dictionary!(T)(); foreach (elem; range) { res.addElement(elem); } return res; }