#986952 (D) No.2780 The Bottle Imp

提出ソース

結果

問題	No.2780 The Bottle Imp
ユーザー	InTheBloom
提出日時	2024-06-07 22:31:22
言語	D (dmd 2.106.1)
結果	AC
実行時間	210 ms / 2,000 ms
コード長	4,877 bytes
コンパイル時間	6,755 ms
コンパイル使用メモリ	176,768 KB
実行使用メモリ	36,380 KB
最終ジャッジ日時	2024-06-08 10:34:42
合計ジャッジ時間	11,016 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	98 ms 16,000 KB
testcase_08	AC	99 ms 16,640 KB
testcase_09	AC	100 ms 16,640 KB
testcase_10	AC	99 ms 16,768 KB
testcase_11	AC	94 ms 16,000 KB
testcase_12	AC	174 ms 22,912 KB
testcase_13	AC	167 ms 22,912 KB
testcase_14	AC	53 ms 11,264 KB
testcase_15	AC	53 ms 11,264 KB
testcase_16	AC	78 ms 11,264 KB
testcase_17	AC	82 ms 11,264 KB
testcase_18	AC	75 ms 11,264 KB
testcase_19	AC	86 ms 11,264 KB
testcase_20	AC	77 ms 11,136 KB
testcase_21	AC	85 ms 11,392 KB
testcase_22	AC	56 ms 9,216 KB
testcase_23	AC	72 ms 9,856 KB
testcase_24	AC	127 ms 15,744 KB
testcase_25	AC	210 ms 18,176 KB
testcase_26	AC	107 ms 14,848 KB
testcase_27	AC	77 ms 14,208 KB
testcase_28	AC	76 ms 14,336 KB
testcase_29	AC	94 ms 17,792 KB
testcase_30	AC	65 ms 9,984 KB
testcase_31	AC	122 ms 16,512 KB
testcase_32	AC	27 ms 6,784 KB
testcase_33	AC	146 ms 33,408 KB
testcase_34	AC	202 ms 36,380 KB
testcase_35	AC	24 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	23 ms 5,376 KB
testcase_39	AC	97 ms 20,992 KB
testcase_40	AC	97 ms 20,864 KB
testcase_41	AC	96 ms 20,864 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB

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

ソースコード

raw source code

import std;

void main () {
    int N = readln.chomp.to!int;
    auto graph = new int[][](N, 0);
    auto revgraph = new int[][](N, 0);

    foreach (i; 0..N) {
        auto input = readln.split.to!(int[]);
        int M = input[0];
        auto A = input[1..$];
        A[] -= 1;

        foreach (j; 0..M) {
            graph[i] ~= A[j];
            revgraph[A[j]] ~= i;
        }
    }

    auto scc = scc_decomposition(graph, revgraph);
    int L = scc.length.to!int;

    auto UF = UnionFind(N);
    foreach (cc; scc) {
        foreach (v; cc) {
            UF.unite(cc[0], v);
        }
    }

    auto dag = new int[][](N, 0);
    foreach (i; 0..N) {
        foreach (to; graph[i]) {
            if (UF.same(i, to)) continue;
            int u = UF.root(i), v = UF.root(to);
            dag[u] ~= v;
        }
    }

    int begin = UF.root(0);

    // もらうdpで判定
    int[int] memo;
    int dp (int pos) {
        if (pos in memo) return memo[pos];
        int res = 1;
        foreach (to; dag[pos]) {
            res = max(res, dp(to) + 1);
        }

        return memo[pos] = res;
    }

    if (dp(begin) == L) {
        writeln("Yes");
    }
    else {
        writeln("No");
    }
}

int[][] scc_decomposition (int[][] graph, int[][] revgraph)
in {
    assert(graph.length == revgraph.length, "graph.length must be equal to revgraph.length");
}
do {
    /**
     * assume:
     * 1. vertex is 0-indexed and maximum vertex number is less than graph.length
     * 2. if graph has edge (u, v), revgraph has edge (v, u).
     *
     * verified with:
     * - yosupo judge | Stringly Connected Components (https://judge.yosupo.jp/problem/scc) (LDC2/632ms/57.90Mib)
     * - AIZU ONLINE JUDGE | 強連結成分分解 (https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C)
     **/

    static bool[] vis;
    static int[] Q;

    vis.length = graph.length;
    Q.length = 0;

    void dfs (int pos) {
        vis[pos] = true;
        foreach (to; graph[pos]) {
            if (vis[to]) continue;
            dfs(to);
        }
        Q ~= pos;
    }

    foreach (i; 0..graph.length) {
        if (!vis[i]) dfs(cast(int) i);
    }

    int[][] scc;
    int idx = 0;
    vis[] = false;
    void revdfs (int pos) {
        vis[pos] = true;
        foreach (to; revgraph[pos]) {
            if (vis[to]) continue;
            revdfs(to);
        }
        scc[idx] ~= pos;
    }

    foreach_reverse (q; Q) {
        if (vis[q]) continue;
        scc ~= new int[](0);
        revdfs(q);
        idx++;
    }

    return scc;
}

class UnionFind_Array {
    /*
     * VERYFYIED
     *   - uniteとsame : yosupo judge (https://judge.yosupo.jp/problem/unionfind)
     *
     * UNVERYFYIED
     *   - countGroups
     *   - GroupSize
     *   - enumGroups
     */
    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 root (int x) 
    in {
        assert(0 <= x && x < N);
    }
    do {
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    bool same (int x, int y)
    in {
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
    }
    do {
        return root(x) == root(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 = root(y);
            smaller = root(x);
        } else {
            larger = root(x);
            smaller = root(y);
        }

        if (larger == smaller) return;

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

    int countGroups () {
        int res = 0;
        foreach (i; 0..N) if (root(i) == i) res++;
        return res;
    }

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

    int[][] enumGroups (int x)
    in {
        assert(0 <= x && x < N);
    }
    do {
        int[][] mp = new int[][](N, 0);
        foreach (i; 0..N) {
            mp[root(i)] ~= i;
        }

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

        return res;
    }

    void reset (int N = this.N)
    in {
        assert(0 <= N, "N must be positive integer.");
    }
    do {
        if (N != this.N) {
            this.N = N;
            parent.length = size.length = N;
        }

        foreach (i; 0..N) {
            parent[i] = i;
            size[i] = 1;
        }
    }
}

auto UnionFind (int N) {
    return new UnionFind_Array(N);
}

yukicoder

結果

テストケース

ソースコード