#928088 (D) No.2536 同値性と充足可能性

提出ソース

結果

問題	No.2536 同値性と充足可能性
ユーザー	InTheBloom
提出日時	2023-11-10 23:19:39
言語	D (dmd 2.106.1)
結果	RE
実行時間	-
コード長	8,274 bytes
コンパイル時間	3,675 ms
コンパイル使用メモリ	168,508 KB
実行使用メモリ	24,948 KB
最終ジャッジ日時	2023-11-10 23:19:54
合計ジャッジ時間	7,649 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	1 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	1 ms 6,676 KB
testcase_09	AC	1 ms 6,676 KB
testcase_10	AC	1 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	1 ms 6,676 KB
testcase_13	AC	1 ms 6,676 KB
testcase_14	AC	1 ms 6,676 KB
testcase_15	AC	2 ms 6,676 KB
testcase_16	AC	1 ms 6,676 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	2 ms 6,676 KB
testcase_19	AC	2 ms 6,676 KB
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	166 ms 17,584 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	163 ms 18,152 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import std;

struct pair {
    int u;
    int v;
}

void main () {
    int N, M; readln.read(N, M);
    pair[] P1;
    pair[] P2;
    foreach (i; 0..M) {
        int u, v;
        string type;
        readln.read(u, type, v);
        u--, v--;
        if (type == "<==>") {
            P1 ~= pair(u, v);
        }
        if (type == "<=/=>") {
            P2 ~= pair(u, v);
        }
    }

    solve(N, M, P1, P2);
}

void solve (int N, int M, pair[] P1, pair[] P2) {
    /* アッ！どっちもとらなくてよい場合があるの忘れてた！ */
    /* すみません。。。作り直します。 */

    /*
       まず、タイプ2の命題で張られる辺をたどっていき、頂点を交互に彩色する。
       ある命題が存在して、違う色を結んでいたら即死亡
       そうでなければ、あとは取る数が足りるかどうかの勝負
       どちらかの色を採用すると決め打ちしてタイプ1命題を探索する。
       タイプ1命題の成すグラフを考えると、連結成分を全部取らないor全部取るしかない。
       取れるやつを全部取る。
     */

    int[][] graph = new int[][](N, 0);
    foreach (p; P2) {
        graph[p.u] ~= p.v;
        graph[p.v] ~= p.u;
    }

    bool isOk = true;
    bool[] visited = new bool[](N);
    int[] color = new int[](N);
    color[] = -1; // -1は未彩色

    void dfs (int pos, int depth) {
        visited[pos] = true;
        /* 矛盾のチェック */
        if (
            (depth % 2 == 0 && color[pos] == 1) ||
            (depth % 2 == 1 && color[pos] == 0)
            )
        {
            isOk = false;
        }

        if (depth % 2 == 0) color[pos] = 0;
        if (depth % 2 == 1) color[pos] = 1;
        foreach (to; graph[pos]) {
            if (!visited[to]) dfs(to, depth+1);
        }
    }

    foreach (p; P2) {
        if (color[p.u] == -1 && color[p.v] == -1) dfs(p.u, 0);
        if (color[p.u] == color[p.v]) enforce(0);
    }

    bool[] used = new bool[](N);
    int[] took;
    /* 命題1の成す連結成分をUFで管理 */
    auto UF = UnionFind!(int)(N);
    foreach (p; P1) {
        UF.unite(p.u, p.v);
    }
    /* 輪から外れてる奴ら */
    int[] unemployed;
    {
        bool[int] mp;
        foreach (g; UF.enumerateGroups) foreach (v; g) mp[v] = true;
        foreach (i; 0..N) if (i !in mp && color[i] == -1) unemployed ~= i;
    }

    bool check (int c) {
        if (!isOk) return false;

        took.length = 0;
        used[] = false;
        foreach (i; 0..N) if (color[i] == c) used[i] = true;

        /* 命題1をとるぜよ */
        foreach (g; UF.enumerateGroups) {
            bool take = true;
            foreach (v; g) {
                if (color[v] == c || color[v] == -1) continue;
                take = false;
                break;
            }
            if (take) foreach (v; g) used[v] = true;
        }

        /* なんも関係ないやつらは勝手にとれるよな？ */
        foreach (u; unemployed) used[u] = true;

        /* 命題1のチェック */
        foreach (p; P1) {
            if (used[p.u] && used[p.v]) continue;
            if (!used[p.u] && !used[p.v]) continue;
            return false;
        }

        foreach (i; 0..N) if (used[i]) took ~= i+1;

        /* 数のチェック */
        if (took.length < (N+2-1)/2) return false;

        writeln("Yes");
        writeln(took.length);
        took.sort;
        foreach (i, t; took) write(t, i == took.length-1 ? '\n' : ' ');
        return true;
    }

    foreach (c; [0, 1]) if (check(c)) return;

    writeln("No");
}

void read(T...)(string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

/**
 * TODO
 *   - クラスの各関数の仕様をまとめる
 *   - コンストラクタ関数の仕様をまとめる
 *   - assertで落としたときにstderrにメッセージを表示
 *   - 関数名を変えるかもしれん(uniteとareInSameGroupとの整合性が取れてなさすぎ)
 *
 * VERYFYIED
 *   - uniteとareInSameGroup : yosupo judge (https://judge.yosupo.jp/problem/unionfind)
 *
 * UNVERYFYIED
 *   - countGroups
 *   - GroupSize
 *   - enumerateGroups
 */


/* ------------------------------ */
/*        class definition        */
/* ------------------------------ */

class UnionFind_Dictionary (T) {
    private:
        T[T] parent;
        int[T] size;

    T findRoot (T x) {
        if (x !in parent) {
            addElement(x);
            return x;
        }

        if (parent[x] == x) return x;
        return parent[x] = findRoot(parent[x]);
    }

    bool areInSameGroup (T x, T y) {
        return findRoot(x) == findRoot(y);
    }

    void unite (T x, T y) {
        addElement(x), addElement(y);
        T larger, smaller;
        if (GroupSize(x) <= GroupSize(y)) {
            larger = findRoot(y);
            smaller = findRoot(x);
        } else {
            larger = findRoot(x);
            smaller = findRoot(y);
        }

        if (larger == smaller) return;

        parent[smaller] = larger;
        size[larger] += size[smaller];
    }

    int countGroups () {
        int res = 0;
        foreach (key, val; parent) {
            if (key == val) 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[findRoot(x)];
    }

    T[][] enumerateGroups (T x) {
        T[][T] mp;
        foreach (key, val; parent) {
            mp[val] ~= key;
        }

        T[][] res = new T[][](mp.length, 0);
        int idx = 0;
        foreach (val; mp) {
            res[idx] = val;
            idx++;
        }

        return res;
    }
}

class UnionFind_Array {
    private:
        int N;
        int[] parent;
        int[] size;

    this (int N)
    in {
        assert(0 <= N, "N must be positive integer.");
    }
    do {
        this.N = N;
        parent = new int[](N);
        size = new int[](N);
        foreach (i; 0..N) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int findRoot (int x) 
    in {
        assert(0 <= x && x < N);
    }
    do {
        if (parent[x] == x) return x;
        return parent[x] = findRoot(parent[x]);
    }

    bool areInSameGroup (int x, int y)
    in {
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
    }
    do {
        return findRoot(x) == findRoot(y);
    }

    void unite (int x, int y)
    in {
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
    }
    do {
        int larger, smaller;
        if (GroupSize(x) <= GroupSize(y)) {
            larger = findRoot(y);
            smaller = findRoot(x);
        } else {
            larger = findRoot(x);
            smaller = findRoot(y);
        }

        if (larger == smaller) return;

        parent[smaller] = larger;
        size[larger] += size[smaller];
    }

    int countGroups () {
        int res = 0;
        foreach (x, par; parent) {
            if (x == par) res++;
        }
        return res;
    }

    int GroupSize (int x)
    in {
        assert(0 <= x && x < N);
    }
    do {
        return size[findRoot(x)];
    }

    int[][] enumerateGroups () {
        int[][] mp = new int[][](N, 0);
        int resSize = 0;
        foreach (i; 0..N) {
            mp[findRoot(i)] ~= i;
        }

        int[][] res;
        foreach (m; mp) {
            if (m.length == 0) continue;
            res ~= m;
        }

        return res;
    }
}

/* ------------------------------ */
/*          Constructors          */
/* ------------------------------ */

/* Dictionary UF */
auto UnionFind (T) () {
    return new UnionFind_Dictionary!(T)();
}

import std.range.primitives : isInputRange;
auto UnionFind (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;
}

/* Array UF */
auto UnionFind (T) (int N) if (is(T == int)) {
    return new UnionFind_Array(N);
}

yukicoder

結果

テストケース

ソースコード