Submission #7138675
Source Code Expand
#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;
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 |
|
Task |
B - Union Find |
User |
m_9719 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2169 Byte |
Status |
AC |
Exec Time |
345 ms |
Memory |
1664 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_01.txt |
All |
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 |
AC |
1 ms |
256 KB |
subtask_01_01.txt |
AC |
217 ms |
640 KB |
subtask_01_02.txt |
AC |
2 ms |
1024 KB |
subtask_01_03.txt |
AC |
334 ms |
1024 KB |
subtask_01_04.txt |
AC |
345 ms |
1664 KB |
subtask_01_05.txt |
AC |
19 ms |
256 KB |
subtask_01_06.txt |
AC |
18 ms |
1024 KB |
subtask_01_07.txt |
AC |
337 ms |
896 KB |
subtask_01_08.txt |
AC |
335 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 |
330 ms |
896 KB |
subtask_01_12.txt |
AC |
342 ms |
1664 KB |
subtask_01_13.txt |
AC |
271 ms |
768 KB |
subtask_01_14.txt |
AC |
2 ms |
1024 KB |
subtask_01_15.txt |
AC |
329 ms |
896 KB |
subtask_01_16.txt |
AC |
345 ms |
1664 KB |
subtask_01_17.txt |
AC |
205 ms |
1408 KB |
subtask_01_18.txt |
AC |
201 ms |
1408 KB |