結果

問題 No.3034 コーエン-マコーレー抽象単体複体
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-21 20:31:25
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 5,356 bytes
コンパイル時間 3,083 ms
コンパイル使用メモリ 101,624 KB
実行使用メモリ 7,792 KB
最終ジャッジ日時 2025-02-06 22:24:10
合計ジャッジ時間 3,586 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

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

import std.algorithm, std.array, std.conv, std.stdio, std.typecons;
alias Edge = Tuple!(uint, uint);
alias EdgeSet = bool[Edge];
alias Face = Tuple!(uint, uint, uint);
alias FaceSet = bool[Face];
alias ASC = Tuple!(EdgeSet, "edges", FaceSet, "faces");
ASC create_normalized_asc(uint[][] face_list, ref uint N) {
    // normalize
    bool[uint] verts;
    foreach (face; face_list) {
        verts[face[0]] = true;
        verts[face[1]] = true;
        verts[face[2]] = true;
    }
    uint[uint] nv;
    uint N2;
    foreach (i; 1 .. N+1) {
        if (i in verts) nv[i] = N2++;
    }
    N = N2;
    
    EdgeSet edges;
    FaceSet faces;
    foreach (face; face_list) {
        edges[Edge(nv[face[0]], nv[face[1]])] = true;
        edges[Edge(nv[face[0]], nv[face[2]])] = true;
        edges[Edge(nv[face[1]], nv[face[2]])] = true;
        faces[Face(nv[face[0]], nv[face[1]], nv[face[2]])] = true;
    }
    
    return ASC(edges, faces);
}
// check if the ASC asc is connected
bool is_connected(ASC asc, uint N) {
    bool[uint] vertex_set;
    auto uf = new UnionFind(N);
    foreach (face; asc.faces.keys) {
        uf.unite(face[0], face[1]);
        uf.unite(face[0], face[2]);
        vertex_set[face[0]] = vertex_set[face[1]] = vertex_set[face[2]] = true;
    }
    foreach (edge; asc.edges.keys) {
        uf.unite(edge[0], edge[1]);
        vertex_set[edge[0]] = vertex_set[edge[1]] = true;
    }
    return uf.size(vertex_set.keys[0]) == vertex_set.length;
}
// calculate link {i} for each i
ASC[] links(ASC asc, uint N) {
    auto result = new ASC[N];
    foreach (face; asc.faces.keys) {
        result[face[0]].edges[Edge(face[1], face[2])] = true;
        result[face[1]].edges[Edge(face[0], face[2])] = true;
        result[face[2]].edges[Edge(face[0], face[1])] = true;
    }
    return result;
}
uint H1_homology_rank(ASC asc, uint N) {
    // dim im d_2
    F_2Vector[] d_2_matrix;
    auto edge_list = asc.edges.keys;
    foreach (face; asc.faces.keys) {
        F_2Vector vec;
        vec.set_entry(cast(uint) edge_list.countUntil(Edge(face[0], face[1])), 1);
        vec.set_entry(cast(uint) edge_list.countUntil(Edge(face[0], face[2])), 1);
        vec.set_entry(cast(uint) edge_list.countUntil(Edge(face[1], face[2])), 1);
        d_2_matrix ~= vec;
    }
    auto b_rank = get_rank(d_2_matrix);
    
    F_2Vector[] d_1_matrix;
    foreach (edge; asc.edges.keys) {
        F_2Vector vec;
        vec.set_entry(edge[0], 1);
        vec.set_entry(edge[1], 1);
        d_1_matrix ~= vec;
    }
    auto z_rank = cast(uint)asc.edges.length - get_rank(d_1_matrix);
    
    assert(z_rank >= b_rank);
    return z_rank - b_rank;
}
void main() {
    auto MN = readln.split.to!(uint[]);
    auto N = MN[0], M = MN[1];
    uint[][] face_list;
    foreach (m; 0 .. M) {
        face_list ~= readln.split.to!(uint[]);
    }
    auto asc = create_normalized_asc(face_list, N);
    
    auto co  = is_connected(asc, N);
    auto dim = H1_homology_rank(asc, N);
    auto lk  = links(asc, N).map!(a => is_connected(a, N)).all!(a => a);
    
    if (!co)           writeln("CO");
    else if (dim != 0) writeln("H1");
    else if (!lk)      writeln("LK");
    else               writeln("CM");
}
/***************************************************************************
****************************************************************************/
alias F_2Vector = ulong[39];        // 39 * 8 > 300
static ulong_size = 8 * (ulong.sizeof);
void set_entry(ref F_2Vector vector, uint n_th, int 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 is_zero(F_2Vector vector) {
    foreach (e; vector) if (e != 0) return false;
    return true;
}
F_2Vector slide_vector(F_2Vector vector) {
    F_2Vector slided;
    foreach (i; 0 .. vector.length - 1) {
        slided[i] = vector[i+1];
    }
    return slided;
}
// by sweep
// vectors can change
uint get_rank(F_2Vector[] vectors ...) {
    if (vectors.all!(v => is_zero(v))) return 0;
    
    // make the left-most vector nonzero
    while (vectors.all!(v => v[0] == 0))
        vectors.each!((ref v) => v = slide_vector(v));
    while (vectors.all!(v => v[0] % 2 == 0))
        vectors.each!((ref v) => v[0] >>= 1);
    foreach (ref v; vectors) {
        if (v[0] % 2 != 0) {
            auto tmp = vectors[0];
            vectors[0] = v;
            v = tmp;
        }
    }
    
    // sweeping
    foreach (ref v; vectors[1 .. $]) {
        if (v[0] % 2 != 0)
            v[] ^= vectors[0][];
    }
    
    vectors[1 .. $].map!((ref v) => v[0] >>= 1);
    return 1 + get_rank(vectors[1 .. $]);
}
// 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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0