結果

問題 No.2316 Freight Train
ユーザー InTheBloomInTheBloom
提出日時 2023-05-31 00:21:21
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 686 ms / 2,000 ms
コード長 2,827 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 162,016 KB
実行使用メモリ 57,584 KB
最終ジャッジ日時 2023-09-04 20:31:16
合計ジャッジ時間 16,799 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 2 ms
4,388 KB
testcase_03 AC 652 ms
53,612 KB
testcase_04 AC 305 ms
21,204 KB
testcase_05 AC 241 ms
22,168 KB
testcase_06 AC 61 ms
6,916 KB
testcase_07 AC 351 ms
22,620 KB
testcase_08 AC 477 ms
53,024 KB
testcase_09 AC 486 ms
41,780 KB
testcase_10 AC 433 ms
21,336 KB
testcase_11 AC 511 ms
57,584 KB
testcase_12 AC 616 ms
39,660 KB
testcase_13 AC 674 ms
52,572 KB
testcase_14 AC 675 ms
54,264 KB
testcase_15 AC 683 ms
53,360 KB
testcase_16 AC 680 ms
53,300 KB
testcase_17 AC 671 ms
54,152 KB
testcase_18 AC 665 ms
53,356 KB
testcase_19 AC 674 ms
54,136 KB
testcase_20 AC 678 ms
53,744 KB
testcase_21 AC 686 ms
54,528 KB
testcase_22 AC 672 ms
53,368 KB
testcase_23 AC 457 ms
54,408 KB
testcase_24 AC 551 ms
54,080 KB
testcase_25 AC 230 ms
10,356 KB
testcase_26 AC 224 ms
9,156 KB
testcase_27 AC 179 ms
4,388 KB
testcase_28 AC 1 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

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