結果

問題 No.3009 Union-Find でつながろう！
ユーザー ジュ・ビオレ・グレイス
提出日時 2024-12-21 23:16:32
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 5,011 bytes
コンパイル時間 2,609 ms
コンパイル使用メモリ 83,840 KB
実行使用メモリ 21,376 KB
最終ジャッジ日時 2025-01-17 20:50:13
合計ジャッジ時間 11,728 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 25 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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;
    }
}
// MAIN PART
// T.length = M
string solve(ulong M, ulong N, BitSet[] Top) {
    auto tree = new UnionFind(N);
    auto M_2 = new BitSet(N), M_3 = new BitSet(M);
    
    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);
            if (j != i) M_2 += j;
        }
        if (i_closure.size > 1) M_3 += i;
    }
    
    size_t ans1;
    foreach (i; 0 .. N) {
        if (tree.root(i) == i) ans1 += 1;
    }
    auto ans2 = M_2.size == N-1 ? "NO" : "YES";
    auto ans3 = M_3.size == N-1 ? "NO" : "YES";
    
    import std.conv: to;
    return ans1.to!string ~ " " ~ ans2 ~ " " ~ ans3;
}
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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0