結果

問題 No.3034 コーエン-マコーレー抽象単体複体
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-24 01:53:53
言語 D
(dmd 2.109.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,072 bytes
コンパイル時間 894 ms
コンパイル使用メモリ 100,952 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-06 22:25:03
合計ジャッジ時間 4,445 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22 RE * 14
権限があれば一括ダウンロードができます

ソースコード

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

import std.algorithm, std.array, std.conv, std.range, std.stdio, std.typecons;
immutable Nmax = 100;
alias Vert = size_t;
alias Edge = Tuple!(Vert, Vert);
alias Face = Tuple!(Vert, Vert, Vert);
class ASC {
    Vert[Vert] nv;      // normalized vertex
    // id := edge_id[ tuple(x, y) ], edge := edges[id];
    // then edge.v1 = x, edge.v2 = y.
    size_t[Edge] edge_id;
    Edge[] edges;
    
    // id := face_id[ tuple(x, y, z) ], face := faces[id];
    // then face.v1 = x, face.v2 = y, face.v3 = z;
    size_t[Face] face_id;
    Face[] faces;
    
    UnionFind uf;           // connectivity
    F_2Vector[] d2, d1;     // homology
    Link[] links;           // links
    
    this () {
        uf = new UnionFind(Nmax);
    }
    
    void add_face(Vert v1, Vert v2, Vert v3) {
        Vert[] added_verts;
        Edge[] added_edges;
        Face[] added_faces;
        
        // start adding
        if (v1 !in nv)
            nv[v1] = nv.length,
            added_verts ~= nv[v1];
        if (v2 !in nv)
            nv[v2] = nv.length,
            added_verts ~= nv[v2];
        if (v3 !in nv)
            nv[v3] = nv.length,
            added_verts ~= nv[v3];
        assert(nv.length <= Nmax);
        
        // normalize
        v1 = nv[v1], v2 = nv[v2], v3 = nv[v3];
        auto _vl = [v1, v2, v3].sort.array;
        v1 = _vl[0], v2 = _vl[1], v3 = _vl[2];
        assert (v1 < v2 && v2 < v3);
        
        if (Edge(v1, v2) !in edge_id)
            edge_id[Edge(v1, v2)] = edges.length,
            edges ~= Edge(v1, v2),
            added_edges ~= Edge(v1, v2);
            
        if (Edge(v1, v3) !in edge_id)
            edge_id[Edge(v1, v3)] = edges.length,
            edges ~= Edge(v1, v3),
            added_edges ~= Edge(v1, v3);
            
        if (Edge(v2, v3) !in edge_id)
            edge_id[Edge(v2, v3)] = edges.length,
            edges ~= Edge(v2, v3),
            added_edges ~= Edge(v2, v3);
            
        if (Face(v1, v2, v3) !in face_id)
            face_id[Face(v1, v2, v3)] = faces.length,
            faces ~= Face(v1, v2, v3),
            added_faces ~= Face(v1, v2, v3);
        
        // calculate connectivity
        foreach (face; added_faces) {
            uf.unite(face[0], face[1], face[2]);
        }
        
        // calculate homology
        foreach (edge; added_edges) {
            F_2Vector vector;
            vector.set_entry(edge[0], true);
            vector.set_entry(edge[1], true);
            add_row(d1, vector);
        }
        foreach (face; added_faces) {
            F_2Vector vector;
            vector.set_entry(edge_id[Edge(face[0], face[1])], true);
            vector.set_entry(edge_id[Edge(face[0], face[2])], true);
            vector.set_entry(edge_id[Edge(face[1], face[2])], true);
            add_row(d2, vector);
        }
        
        // calculate links
        links.length += added_verts.length;
        foreach (vert; added_verts) {
            auto link = new Link(vert);
            links[vert] = link;
        }
        foreach (face; added_faces) {
            links[face[0]].add_edge(Edge(face[1], face[2]));
            links[face[1]].add_edge(Edge(face[0], face[2]));
            links[face[2]].add_edge(Edge(face[0], face[1]));
        }
    }
    
    // connectivity
    bool is_connected() {
        return uf.size(faces[0][0]) == nv.length;
    }
    
    // homology
    size_t dim_H_1() {
        auto dim_im_d2 = d2.length;
        auto dim_im_d1 = d1.length;
        auto dim_ker_d1 = edges.length - dim_im_d1;
        assert(dim_ker_d1 >= dim_im_d2);
        return dim_ker_d1 - dim_im_d2;
    }
    
    // keeping row echolon form
    void add_row(ref F_2Vector[] matrix, F_2Vector vector) {
        foreach (j, row; matrix) {
            auto iv = vector.least_nonzero_index();
            auto ir = row.least_nonzero_index();
            assert(ir != -1);
            
            if (iv == -1)   // vector is linearly dependent
                return;
            else if (iv < ir) { // insert v
                matrix = matrix[0 .. j] ~ [vector] ~ matrix[j .. $];
                return;
            }
            else if (iv == ir) {
                vector[] ^= row[];  // sweep
            }
        }
        if (!vector.is_zero()) matrix ~= vector;
    }
    
    // link {i} 
    class Link {
        bool[Vert] vert_set;
        Vert of_vert;
        UnionFind lkuf;
        
        this (Vert vert) {
            this.of_vert = vert;
            lkuf = new UnionFind(Nmax); 
        }
        
        void add_edge(Edge edge) {
            vert_set[edge[0]] = true;
            vert_set[edge[1]] = true;
            lkuf.unite(edge[0], edge[1]);
        }
        
        bool is_connected() {
            return lkuf.size(vert_set.keys[0]) == vert_set.length;
        }
    }
}
void main() {
    auto MN = readln.split.to!(size_t[]);
    auto N = MN[0], M = MN[1];
    size_t[][] face_list;
    foreach (m; 0 .. M) {
        face_list ~= readln.split.to!(size_t[]);
    }
    
    auto asc = new ASC;
    foreach (i, face; face_list) {
        asc.add_face(face[0], face[1], face[2]);
        if (!asc.is_connected)
            writeln("CO");
        else if (asc.dim_H_1 != 0)
            writeln("H1");
        else if (!asc.links.all!(link => link.is_connected))
            writeln("LK");
        else
            writeln("CM");
    }
    
    /+foreach (i, link; asc.links) {
        writeln(i+1);
        foreach (vert; link.vert_set.keys) {
            writefln("    (%d->%d) ", vert+1, link.lkuf.root(vert)+1);
        }
    }+/
}
/***************************************************************************
****************************************************************************/
alias F_2Vector = size_t[5];        // 5 * 64 > 300
immutable ulong_size = 8 * (size_t.sizeof);
immutable vector_size = 300;
void set_entry(ref F_2Vector vector, size_t n_th, bool val) {
    if (val)
        vector[n_th / ulong_size] |= 1UL << n_th % ulong_size;
    else
        vector[n_th / ulong_size] &= ~0UL - (1UL << (n_th % ulong_size));
}
bool get_entry(F_2Vector vector, size_t n_th) {
    return (vector[n_th / ulong_size] & (1UL << n_th % ulong_size)) != 0;
}
bool is_zero(F_2Vector vector) {
    foreach (e; vector) if (e != 0) return false;
    return true;
}
// return -1 if vector == 0
auto least_nonzero_index(F_2Vector vector) {
    return iota(vector_size).countUntil!(i => vector.get_entry(i));
}
/+
// to row echolon form
F_2Vector[] reform(ref F_2Vector[] matrix) {
    size_t j;
    foreach (i; 0 .. matrix.length) {
        while (j < vector_size) {
            // find nonzero entry
            foreach (i2; i .. matrix.length) {
                if (get_entry(matrix[i2], j)) {
                    swap(matrix[i2], matrix[i]);
                    break;
                }
            }
        
            // all zero
            if (!get_entry(matrix[i], matrix[i2])) {
                ++j;
            }
            else {
                // sweeping
                foreach (i2; i+1 .. matrix.length) {
                if (get_entry(matrix[i2], j)) matrix[i2] ^= matrix[i];
                ++j;
                break;
            }
        }
    }
}
+/
// 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[] mlist...) {
        assert(n < num);
        bool result;
        foreach (m; mlist) {
            assert(m < num);
            auto rn = root(n), rm = root(m);
            if (rn == rm) continue;
            // 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;
            result = true;
        }
        return result;
    }
    
    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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0