AtCoder Typical Contest 001

Submission #7123061

Source codeソースコード

#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

struct union_find_tree{
    vector<long long> par;
    vector<long long> rank;
    union_find_tree(long long n){
        init(n);
    }

    void init(long long n){
        for(long long i=0;i<n;i++){
            par.push_back(i);
            rank.push_back(0);
        }
    }

    long long find(long long a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }

    void unite(long long a,long long b){
        long long root_a=find(a);
        long long root_b=find(b);
        if(root_a==root_b)return;
        if(rank[root_a]<rank[root_b]){
            par[root_a]=root_b;
        }else if(rank[root_a]>rank[root_b]){
            par[root_b]=root_a;
        }else{
            par[root_a]=root_b;
            rank[root_a]++;
        }
    }

    bool same(long long a,long long b){
        return find(a) == find(b);
    }

};

int main(){
    ll n,q;
    cin>>n>>q;
    union_find_tree uft(n);
    rep(i,q){
        ll p,a,b;
        cin>>p>>a>>b;
        if(p==0){
            uft.unite(a,b);
        }else{
            if(uft.same(a,b)){
                cout<<"Yes"<<endl;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
}

Submission

Task問題 B - Union Find
User nameユーザ名 miotsukushi
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1363 Byte
File nameファイル名
Exec time実行時間 457 ms
Memory usageメモリ使用量 2668 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 271 ms 896 KB
subtask_01_02.txt AC 3 ms 2036 KB
subtask_01_03.txt AC 411 ms 1024 KB
subtask_01_04.txt AC 450 ms 2668 KB
subtask_01_05.txt AC 24 ms 256 KB
subtask_01_06.txt AC 26 ms 2036 KB
subtask_01_07.txt AC 422 ms 896 KB
subtask_01_08.txt AC 452 ms 2668 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 3 ms 2036 KB
subtask_01_11.txt AC 403 ms 896 KB
subtask_01_12.txt AC 450 ms 2668 KB
subtask_01_13.txt AC 345 ms 768 KB
subtask_01_14.txt AC 4 ms 2036 KB
subtask_01_15.txt AC 409 ms 896 KB
subtask_01_16.txt AC 457 ms 2668 KB
subtask_01_17.txt AC 309 ms 2412 KB
subtask_01_18.txt AC 304 ms 2412 KB