Submission #7973608


Source Code Expand

#include <iostream>

using namespace std;

typedef long long ll;

ll par[100010];
ll sz[100010];

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

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

void unite(ll x, ll 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(ll x, ll y) {
    return par[x] == par[y];
}

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

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

    return 0;
}

Submission Info

Submission Time
Task B - Union Find
User isawo
Language C++14 (Clang 3.8.0)
Score 100
Code Size 1091 Byte
Status AC
Exec Time 726 ms
Memory 7040 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
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 2 ms 512 KB
subtask_01_01.txt AC 412 ms 3584 KB
subtask_01_02.txt AC 2 ms 1792 KB
subtask_01_03.txt AC 581 ms 5760 KB
subtask_01_04.txt AC 718 ms 7040 KB
subtask_01_05.txt AC 39 ms 640 KB
subtask_01_06.txt AC 43 ms 2176 KB
subtask_01_07.txt AC 628 ms 5504 KB
subtask_01_08.txt AC 726 ms 7040 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 2 ms 1792 KB
subtask_01_11.txt AC 589 ms 5632 KB
subtask_01_12.txt AC 725 ms 7040 KB
subtask_01_13.txt AC 539 ms 4480 KB
subtask_01_14.txt AC 3 ms 1792 KB
subtask_01_15.txt AC 617 ms 5504 KB
subtask_01_16.txt AC 712 ms 7040 KB
subtask_01_17.txt AC 563 ms 6784 KB
subtask_01_18.txt AC 553 ms 6784 KB