Submission #7973449


Source Code Expand

#include <iostream>

using namespace std;

int par[10010];
int sz[100010];

void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 0;
    }
}

int find(int x) {
    if (par[x] == x)
        return x;
    else 
        return par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y]) {
        par[x] = y;
    }
    else {
        par[y] = x;
        if (sz[x] == sz[y])
            sz[x]++;
    }
}

bool same(int x, int y) {
    return par[x] == par[y];
}

int main() {
    int n, q;   cin >> n >> q;
    int *p = new int[q], *a = new int[q], *b = new int[q];
    init(n);
    for (int i = 0; i < q; i++)
        cin >> p[i] >> a[i] >> b[i];

    for (int i = 0; i < q; i++) {
        if (p[i]) {
            if (same(a[i]-1, b[i]-1))
                cout << "Yes" << endl;
            else 
                cout << "No" << endl;
        }
        else 
            unite(a[i]-1, b[i]-1);
    }

    return 0;
}

Submission Info

Submission Time
Task B - Union Find
User isawo
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1089 Byte
Status WA
Exec Time 735 ms
Memory 4736 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 1
AC × 13
WA × 6
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 1 ms 256 KB
subtask_01_01.txt AC 421 ms 2048 KB
subtask_01_02.txt AC 1 ms 640 KB
subtask_01_03.txt AC 594 ms 3456 KB
subtask_01_04.txt AC 721 ms 3584 KB
subtask_01_05.txt AC 38 ms 512 KB
subtask_01_06.txt AC 43 ms 896 KB
subtask_01_07.txt WA 648 ms 3200 KB
subtask_01_08.txt AC 728 ms 3584 KB
subtask_01_09.txt WA 1 ms 256 KB
subtask_01_10.txt AC 2 ms 640 KB
subtask_01_11.txt WA 594 ms 3200 KB
subtask_01_12.txt AC 720 ms 3584 KB
subtask_01_13.txt AC 539 ms 2560 KB
subtask_01_14.txt AC 3 ms 640 KB
subtask_01_15.txt WA 639 ms 3200 KB
subtask_01_16.txt AC 735 ms 3584 KB
subtask_01_17.txt WA 566 ms 4736 KB
subtask_01_18.txt WA 564 ms 3328 KB