Submission #5239817
Source Code Expand
#define _GLIBCXX_DEBUG
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define whlie while
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 1001001001
#define mod 1000000007
#define FOR(i,a,b) for(int (i)=((int)a); (i)<((int)b); (i)++) // [a,b)
#define rep(i,N) FOR((i), 0, ((int)N)) // [0,N)
#define FORR(i,a,b) for(int (i)=((int)b) - 1; (i)>=((int)a); (i)--)
#define repr(i,N) FORR((i), 0, ((int)N))
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it=v.begin();it<v.end();it++)
#define vrepr(v,it) for(auto it=v.rbegin();it<v.rend();it++)
#define inx(t,...) t __VA_ARGS__; in(__VA_ARGS__)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) double __VA_ARGS__; in(__VA_ARGS__)
#define inpii(...) pii __VA_ARGS__; in(__VA_ARGS__)
#define invi(v,...) vi v; in(v,##__VA_ARGS__)
#define invl(v,...) vl v; in(v,##__VA_ARGS__)
// デバッグ用
// dbg(...) printfと同様に使用可能
// trc(var) (変数名)=(値)と表示
// stopif(val) 条件分が真の時に止まる
// vd(v,N) vの中身を表示
#ifdef LOCAL
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define trc(...) cout << #__VA_ARGS__ << "="; dbg_out(__VA_ARGS__)
#define stopif(val) assert( !(val) )
#define vdbg(v,...) cout << #v << "={"; vector_debug(v , ##__VA_ARGS__)
#else
#define dbg(...) 1
#define trc(...) 1
#define stopif(...) 1
#define vdbg(...) 1
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector< vector<int> > vvi;
int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);}
int lcm(int a, int b){return (a / gcd(a,b)) * b;} ll lcm(ll a, ll b){return (a / gcd(a,b)) * b;}
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename C> inline void _cin(C &c){cin >> c;} template<typename T,typename U> inline void _cin(pair<T,U> &p){cin >> p.fi; cin >> p.se;}
template<typename C> inline void _cout(const C &c){cout << c;} template<typename T,typename U> inline void _cout(const pair<T,U> &p){cout << p.fi << ' ' << p.se;}
void in(){} template <typename T,class... U> void in(T &t,U &...u){ _cin(t); in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ' '; out(u...);}
void dbg_out(){cout << endl;} template <typename T,class... U> void dbg_out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ','; out(u...);}
template<typename C> inline void in(vector<C> &v,int N=-1){if(sz(v) != 0){int M=(N == -1) ? sz(v) : N; rep(i,M) _cin(v[i]);}else{C c;rep(i,N) v.pb((_cin(c),c));}} template<typename C> inline void in(C v[],int N){rep(i,N) _cin(v[i]);}
template<typename C> inline void out(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; } template<typename C> inline void out(C v[],int N){rep(i,N) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; }
template<typename C> inline void vector_debug(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?", ":"" ); _cout(v[i]);} cout<<"}"<<endl; } template<typename C> inline void vector_debug(C v[], int N){rep(i,N) {cout<<((i)?", ":""); _cout(*(v+i));} cout<<"}"<<endl;}
template<typename C> inline C vmax(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amax(n,v[i]); return n;} template<typename C> inline C vmax(C v[], int N){C n=v[0]; rep( i , N ) amax(n,v[i]); return n;}
template<typename C> inline C vmin(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amin(n,v[i]); return n;} template<typename C> inline C vmin(C v[], int N){C n=v[0]; rep( i , N ) amin(n,v[i]); return n;}
template<typename C> inline C vsum(const vector<C> &v){C n=0; rep(i,sz(v)) n+=v[i]; return n;} template<typename C> inline C vsum(C v[], int N){C n=0; rep( i , N ) n+=v[i]; return n;}
const int dx[]={1,0,-1,0}; const int dy[]={0,1,0,-1};
//const int dx[]={1,1,1,0,-1,-1,-1,0}; const int dy[]={1,0,-1,-1,-1,0,1,1};
// ini(A,B,C) => int A,B,C; cin >> A >> B >> C;
// in(A,B,C) => cin >> A >> B >> C; invi(v,N) =>vi v; rep(i,N) v.pb( (int x,cin >> x,x) );
// out(A,B,C) cout << A << ' ' << B << ' ' << C;
// in,outともにベクトル・配列・pairに使用可能(ただしベクトル・配列は1つしか入れられない)
// amax(x,y) bool関数 x<yの時にxにyを代入してtrueを返す
struct UF{
vector<int> par,rank;
UF(int N) : par(N),rank(N){
for(int i=0; i<N; i++) par[i]=i,rank[i]=0;
}
int find(int x){
return par[x]==x ? x : par[x] = find(par[x]);
}
bool same(int x,int y){
return find(x) == find(y);
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]){
par[x] = y;
} else {
par[y] = x;
if(rank[x]==rank[y]) rank[x]++;
}
}
};
int main(){
ini(N,Q);
UF uf(N);
rep(hoge,Q){
ini(P,A,B);
if(P == 0){
uf.unite(A,B);
}
else{
out(uf.same(A,B) ? "Yes" : "No");
}
}
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
Nyaan |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6058 Byte |
Status |
AC |
Exec Time |
474 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 |
270 ms |
640 KB |
subtask_01_02.txt |
AC |
2 ms |
1024 KB |
subtask_01_03.txt |
AC |
418 ms |
1024 KB |
subtask_01_04.txt |
AC |
474 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 |
431 ms |
896 KB |
subtask_01_08.txt |
AC |
468 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 |
417 ms |
896 KB |
subtask_01_12.txt |
AC |
473 ms |
1664 KB |
subtask_01_13.txt |
AC |
354 ms |
768 KB |
subtask_01_14.txt |
AC |
3 ms |
1024 KB |
subtask_01_15.txt |
AC |
445 ms |
768 KB |
subtask_01_16.txt |
AC |
474 ms |
1664 KB |
subtask_01_17.txt |
AC |
308 ms |
1408 KB |
subtask_01_18.txt |
AC |
310 ms |
1408 KB |