Submission #7103450


Source Code Expand

Copy
#include<iostream>
#include<vector>
using namespace std;
#define rep(i, j, n) for (int i = j; i < n; i++);
typedef pair<int,int>P;

struct UnionFind{
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) : parent(n),rank(n) {
        for(int i=0;i<n;i++){
            parent[i]=i;
            rank[i]=0;
        }
    }

    int root(int x){
        if(parent[x]==x)return x;
        return parent[x]=root(parent[x]);
    }

    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry)return ;

        if(rank[rx]<rank[ry])parent[rx]=ry;
        else {
            parent[ry]=rx;
            if(rank[rx]==rank[ry])rank[rx]++;
        }
    }

    bool same(int x,int y){
        int rx=root(x),ry=root(y);
        return rx==ry;
    }
};

int main(){
    int n,q;cin>>n>>q;
    UnionFind uf(n);
    for(int i=0;i<q;i++){
        int p,x,y;
        cin>>p>>x>>y;
        if(p==0)uf.unite(x,y);
        else{
        if(uf.same(x,y))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        }
    }
    return 0;
}

Submission Info

Submission Time
Task B - Union Find
User bio4eta
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1103 Byte
Status
Exec Time 459 ms
Memory 1664 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt
All 100 / 100 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 1 ms 256 KB
subtask_01_01.txt 270 ms 640 KB
subtask_01_02.txt 2 ms 1024 KB
subtask_01_03.txt 408 ms 1024 KB
subtask_01_04.txt 453 ms 1664 KB
subtask_01_05.txt 25 ms 256 KB
subtask_01_06.txt 26 ms 1024 KB
subtask_01_07.txt 435 ms 896 KB
subtask_01_08.txt 453 ms 1664 KB
subtask_01_09.txt 1 ms 256 KB
subtask_01_10.txt 2 ms 1024 KB
subtask_01_11.txt 408 ms 896 KB
subtask_01_12.txt 459 ms 1664 KB
subtask_01_13.txt 345 ms 768 KB
subtask_01_14.txt 3 ms 1024 KB
subtask_01_15.txt 415 ms 768 KB
subtask_01_16.txt 455 ms 1664 KB
subtask_01_17.txt 303 ms 1408 KB
subtask_01_18.txt 307 ms 1408 KB