結果

問題 No.2316 Freight Train
コンテスト
ユーザー InTheBloom
提出日時 2023-05-31 00:21:21
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 528 ms / 2,000 ms
コード長 2,827 bytes
コンパイル時間 1,442 ms
コンパイル使用メモリ 174,280 KB
実行使用メモリ 56,208 KB
最終ジャッジ日時 2024-06-22 18:04:05
合計ジャッジ時間 13,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N, Q;
    {
        auto buf = readln.split.to!(int[]);
        N = buf[0], Q = buf[1];
    }

    solve(N, Q);
}

void solve (int N, int Q) {
    auto P = readln.split.to!(int[]);
    auto UF = UnionFind!int();
    foreach (i, x; P) {
        if (x != -1) {
            UF.merge_group(cast(int)i+1, x);
        }
    }
    foreach (_; 0..Q) {
        int A, B;
        {
            auto buf = readln.split.to!(int[]);
            A = buf[0], B = buf[1];
        }
        if (UF.is_same_group(A, B)) {
            writeln("Yes");
        } else {
            writeln("No");
        }
    }
}

struct UnionFind(T) {
    T[T] parent;
    int[T] size;

    // どの要素が一番上の親かを返す。途中経由した頂点もparentの内容がすべて更新される。
    // privateを外しても問題ないが、同一グループ判定にはis_same_group()を使うべき
    private T root (T x) {
        if (parent[x] != x) {
            parent[x] = root(parent[x]);
        }
        return parent[x];
    }

    // 素集合の数を返す。
    int num_of_group () {
        int ret = 0;
        foreach (key, elem; parent) {
            if (key == elem) {
                ret++;
            }
        }
        return ret;
    }

    // 素集合系に要素を(要素数1の集合として)登録する。
    // これをしないと孤立した頂点は系に存在しないものとして扱われ、num_of_group()が正常に動かない。
    // 他の関数は影響を受けない。
    bool register (T x) {
        if (x !in parent) {
            parent[x] = x;
            size[x] = 1;
        }
        return false;
    }

    // ２つの要素が同一集合に属しているかを判定する。
    bool is_same_group (T x, T y) {
        if (x == y) {
            return true;
        }

        if (x !in parent || y !in parent) {
            return false;
        }

        T parx = root(x), pary = root(y);
        return parx == pary;
    }

    // それぞれの要素が属する集合を併合する。
    bool merge_group (T x, T y) {
        if (x == y) {
            return false;
        }

        if (x !in parent) {
            parent[x] = x;
            size[x] = 1;
        }
        if (y !in parent) {
            parent[y] = y;
            size[y] = 1;
        }

        T parx = root(x), pary = root(y);

        if (size[parx] > size[pary]) {
            size[parx] += size[pary];
            parent[pary] = parx;
        } else {
            size[pary] += size[parx];
            parent[parx] = pary;
        }

        return true;
    }

    // 要素が属する集合の要素数を返す。
    int sizeof_group (T x) {
        if (x !in parent) {
            return 1;
        }
        return size[root(x)];
    }
}
0