結果
問題 |
No.3009 Union-Find でつながろう!
|
ユーザー |
![]() |
提出日時 | 2024-12-22 00:01:09 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 1,022 ms / 2,000 ms |
コード長 | 4,786 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 83,200 KB |
実行使用メモリ | 21,248 KB |
最終ジャッジ日時 | 2025-01-17 20:50:24 |
合計ジャッジ時間 | 9,617 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
// treat subsets of {0, 1, ..., n-1} class BitSet { static immutable bit_size = 8 * size_t.sizeof; size_t n; // number of elements private size_t data_size; private size_t[] data; size_t[] to_data(size_t[] elements) { auto result = new size_t[data_size]; foreach (elem; elements) { assert(elem < n); auto q = elem / bit_size; auto r = elem % bit_size; result[q] |= (1UL << r); } return result; } this (size_t n, size_t[] elements ...) { this.n = n; this.data_size = n % bit_size == 0 ? n/bit_size : n/bit_size + 1; this.data = to_data(elements); } BitSet opUnary(string op : "~")() { auto result = this; result.data[] = ~(result.data[]); return result; } // set operations BitSet opBinary(string op)(BitSet rhs) { auto result = this; static if (op == "*" || op == "&") { result.data[] &= rhs.data[]; } else if (op == "-") { result.data[] &= ~(rhs.data[]); } else if (op == "+" || op == "|") { result.data[] |= rhs.data[]; } else assert(0); return result; } BitSet opBinary(string op)(size_t[] rhs ...) { return opBinary!op(new BitSet(n, rhs)); } BitSet opOpAssign(string op)(BitSet rhs) { static if (op == "*" || op == "&") { this.data[] &= rhs.data[]; } else if (op == "-") { this.data[] &= ~(rhs.data[]); } else if (op == "+" || op == "|") { this.data[] |= rhs.data[]; } else assert(0); return this; } BitSet opOpAssign(string op)(size_t[] rhs ...) { return opOpAssign!op(new BitSet(n, rhs)); } bool opBinaryRight(string op : "in")(size_t lhs) { assert(lhs < n); auto q = lhs / bit_size; auto r = lhs % bit_size; return (data[q] & (1UL << r)) != 0; } bool opBinaryRight(string op : "in")(size_t[] lhs) { bool result = true; foreach (elem; lhs) result = result && (elem in this); return result; } size_t[] to_elements() { size_t[] result; foreach (q; 0 .. data_size) foreach (r; 0 .. bit_size) { auto i = q * bit_size + r; if (i >= n) break; if (data[q] & (1UL << r)) result ~= i; } return result; } size_t size() { size_t result; foreach (q; 0 .. data_size) foreach (r; 0 .. bit_size) { auto i = q * bit_size + r; if (i >= n) break; if (data[q] & (1UL << r)) ++result; } return result; } } // Union-tree of {0, 1, ..., num-1} class UnionFind { size_t num; private size_t[] parent; private size_t[] rank; private size_t[] size_; this (size_t num) { this.num = num; parent.length = num; foreach (n; 0 .. num) parent[n] = n; rank.length = num; size_.length = num; } size_t root(size_t n) { assert(n < num); if (parent[n] == n) return n; else return parent[n] = root(parent[n]); // recursively set the root } bool is_same(size_t n, size_t m) { assert(n < num && m < num); return root(n) == root(m); } // false if already united bool unite(size_t n, size_t m) { assert(n < num && m < num); auto rn = root(n), rm = root(m); if (rn == rm) return false; // swap if necessary to force rank[rm] <= rank[rn] if (rank[rn] < rank[rm]) { auto tmp = rm; rm = rn; rn = tmp; } parent[rm] = rn; if (rank[rn] == rank[rm]) ++rank[rn]; size_[rn] += size_[rm] + 1; return true; } size_t size(size_t n) { return size_[root(n)]+1; } size_t size() { size_t result; foreach (i; 0 .. num) if (root(i) == i) result += 1; return result; } } // MAIN PART // T.length = M ulong solve(ulong M, ulong N, BitSet[] Top) { auto tree = new UnionFind(N); foreach (i; 0 .. N) { // calculate the closure of {i} auto i_closure = new BitSet(N); foreach (U; Top) { if (i !in U) i_closure |= U; } i_closure = ~ i_closure; // for each j in the closure of {i} foreach (j; 0 .. N) if (j in i_closure) tree.unite(i, j); } return tree.size; } void main() { import std.stdio, std.conv, std.array; ulong M, N; { auto MN = readln().split(); M = MN[0].to!ulong; N = MN[1].to!ulong; } // make the data of subsets auto Top = new BitSet[M]; foreach (m; 0 .. M) { Top[m] = new BitSet(N); auto bits = readln(); foreach (i; 0 .. N) // remove the last \n if (bits[i] == '1') Top[m] += i; } solve(M, N, Top).writeln(); }