AtCoder Typical Contest 001

Submission #420855

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF 1<<30
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define ll long long
#define ull unsigned long long
struct uf{
	vector<int> parent;
	vector<int> rank;
	int n;
	void init(int N){n=N;parent.reserve(n);rank.reserve(n);REP(i,n){parent[i]=i;rank[i]=0;}}
	int  root(int x){return (parent[x]==x)? x: parent[x];}
	bool same(int x,int y){return root(x)==root(y);}
	void unite(int x, int y){
		x=root(x);y=root(y);
		if(x==y)return;
		if(rank[x]<rank[y])parent[x]=y;
		else{
			parent[y]=x;
			if(rank[x]==rank[y])rank[x]++;
		}
	}
};
int main(){
	int n,m;cin>>n>>m;
	uf Union;
	Union.init(n);
	REP(i,m){
		int f,x,y;cin>>f>>x>>y;
		if(f==0){Union.unite(x,y);}
		else{
			if(Union.same(x,y))cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
		
	}

	return 0;
}

Submission

Task問題 B - Union Find
User nameユーザ名 070_ish_774
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 1239 Byte
File nameファイル名
Exec time実行時間 981 ms
Memory usageメモリ使用量 1696 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 26 ms 920 KB
subtask_01_01.txt AC 562 ms 808 KB
subtask_01_02.txt AC 27 ms 1572 KB
subtask_01_03.txt AC 915 ms 928 KB
subtask_01_04.txt AC 900 ms 1576 KB
subtask_01_05.txt AC 75 ms 804 KB
subtask_01_06.txt AC 78 ms 1560 KB
subtask_01_07.txt AC 790 ms 804 KB
subtask_01_08.txt AC 981 ms 1696 KB
subtask_01_09.txt AC 27 ms 796 KB
subtask_01_10.txt AC 28 ms 1564 KB
subtask_01_11.txt AC 687 ms 920 KB
subtask_01_12.txt AC 932 ms 1568 KB
subtask_01_13.txt AC 568 ms 920 KB
subtask_01_14.txt AC 30 ms 1568 KB
subtask_01_15.txt AC 846 ms 812 KB
subtask_01_16.txt AC 977 ms 1572 KB
subtask_01_17.txt AC 694 ms 1568 KB
subtask_01_18.txt AC 684 ms 1572 KB