結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー InTheBloom
提出日時 2024-06-07 22:31:22
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 4,877 bytes
コンパイル時間 5,306 ms
コンパイル使用メモリ 176,640 KB
実行使用メモリ 36,380 KB
最終ジャッジ日時 2024-12-27 14:10:32
合計ジャッジ時間 9,821 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);
}
0