結果

問題 No.2316 Freight Train
ユーザー InTheBloomInTheBloom
提出日時 2023-05-31 00:21:21
言語 D
(dmd 2.106.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 499 ms
53,308 KB
testcase_04 AC 238 ms
20,144 KB
testcase_05 AC 190 ms
21,040 KB
testcase_06 AC 50 ms
6,944 KB
testcase_07 AC 284 ms
21,652 KB
testcase_08 AC 364 ms
52,136 KB
testcase_09 AC 378 ms
40,304 KB
testcase_10 AC 336 ms
21,688 KB
testcase_11 AC 399 ms
56,208 KB
testcase_12 AC 471 ms
38,708 KB
testcase_13 AC 516 ms
52,428 KB
testcase_14 AC 522 ms
53,288 KB
testcase_15 AC 519 ms
51,632 KB
testcase_16 AC 516 ms
53,040 KB
testcase_17 AC 518 ms
52,216 KB
testcase_18 AC 516 ms
51,660 KB
testcase_19 AC 517 ms
52,236 KB
testcase_20 AC 528 ms
52,172 KB
testcase_21 AC 528 ms
52,428 KB
testcase_22 AC 523 ms
51,804 KB
testcase_23 AC 378 ms
51,948 KB
testcase_24 AC 448 ms
52,124 KB
testcase_25 AC 193 ms
8,496 KB
testcase_26 AC 188 ms
9,916 KB
testcase_27 AC 156 ms
6,944 KB
testcase_28 AC 1 ms
6,940 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