AtCoder Typical Contest 001

Submission #7103450

Source codeソースコード

#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

Task問題 B - Union Find
User nameユーザ名 bio4eta
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1103 Byte
File nameファイル名
Exec time実行時間 459 ms
Memory usageメモリ使用量 1664 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 1 ms 256 KB
subtask_01_01.txt AC 270 ms 640 KB
subtask_01_02.txt AC 2 ms 1024 KB
subtask_01_03.txt AC 408 ms 1024 KB
subtask_01_04.txt AC 453 ms 1664 KB
subtask_01_05.txt AC 25 ms 256 KB
subtask_01_06.txt AC 26 ms 1024 KB
subtask_01_07.txt AC 435 ms 896 KB
subtask_01_08.txt AC 453 ms 1664 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 2 ms 1024 KB
subtask_01_11.txt AC 408 ms 896 KB
subtask_01_12.txt AC 459 ms 1664 KB
subtask_01_13.txt AC 345 ms 768 KB
subtask_01_14.txt AC 3 ms 1024 KB
subtask_01_15.txt AC 415 ms 768 KB
subtask_01_16.txt AC 455 ms 1664 KB
subtask_01_17.txt AC 303 ms 1408 KB
subtask_01_18.txt AC 307 ms 1408 KB