Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #7138343

Source Code Expand

Copy
```#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
std::fill( (T*)array, (T*)(array+N), val );
}
__attribute__((constructor))
void initial(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}

// UnionFind
struct UnionFind{
VI par,sizes; // par[i]:iの親の番号
UnionFind(int n) : par(n), sizes(n,1){ // 最初は全てが根であるとして初期化
rep(i,n) par[i] = i;
}
int root(int x){
if(par[x]==x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y){
int rx = root(x); int ry = root(y);
if(rx==ry) return;
if(sizes[rx]<sizes[ry]) swap(rx,ry);
par[ry] = rx;
sizes[rx] += sizes[ry];
}
bool same(int x, int y){
return root(x)==root(y);
}
int size(int x){
return sizes[root(x)];
}
};

signed main(){
int n,q; cin>>n>>q;
UnionFind tree(n);
rep(i,q){
int p,a,b; cin>>p>>a>>b; a--; b--;
if(p){
if(tree.same(a,b)) cout << "Yes" << endl;
else cout << "No" << endl;
}else{
tree.unite(a,b);
}
}
return 0;
}
```

#### Submission Info

Submission Time 2019-08-25 21:20:49+0900 B - Union Find m_9719 C++14 (GCC 5.4.1) 0 2179 Byte WA 348 ms 1664 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt
Case Name Status Exec Time Memory
00_sample_01.txt 1 ms 256 KB
subtask_01_01.txt 207 ms 640 KB
subtask_01_02.txt 2 ms 1024 KB
subtask_01_03.txt 338 ms 1024 KB
subtask_01_04.txt 340 ms 1664 KB
subtask_01_05.txt 20 ms 256 KB
subtask_01_06.txt 18 ms 1024 KB
subtask_01_07.txt 340 ms 896 KB
subtask_01_08.txt 348 ms 1664 KB
subtask_01_09.txt 1 ms 256 KB
subtask_01_10.txt 2 ms 1024 KB
subtask_01_11.txt 337 ms 896 KB
subtask_01_12.txt 341 ms 1664 KB
subtask_01_13.txt 276 ms 768 KB
subtask_01_14.txt 2 ms 1024 KB
subtask_01_15.txt 341 ms 896 KB
subtask_01_16.txt 348 ms 1664 KB
subtask_01_17.txt 208 ms 1408 KB
subtask_01_18.txt 200 ms 1408 KB