Submission #1334930
Source Code Expand
#ifdef LOCAL111
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }
//library
class UFTree {
//private:
public:
vector<int> par;
vector<int> rank;
vector<int> num;
//public:
UFTree(int n)
{
par = vector<int>(n);
rank = vector<int>(n);
num = vector<int>(n);
for(int i = 0; i < n; i++){
par[i] = i;
rank[i] = 0;
num[i] = 1;
}
}
int find(int x)
{
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]){
par[x] = y;
num[y] += num[x];
}else{
par[y] = x;
num[x] += num[y];
if(rank[x] == rank[y]) rank[x]++;
}
}
int count(int x)
{
return num[find(x)];
}
bool same(int x, int y)
{
return find(x) == find(y);
}
};
//library
#define endl '\n'
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) int((a).size())
#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(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
#define DEBUG(x) true
template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
void ios_init(){
//cout.setf(ios::fixed);
//cout.precision(12);
#ifdef LOCAL111
return;
#endif
ios::sync_with_stdio(false); cin.tie(0);
}
int main()
{
ios_init();
int n,q;
cin >> n >> q;
UFTree uf(n);
REP(_,q){
int p, a, b;
cin >> p >> a >> b;
if(p == 0){
uf.unite(a,b);
}else{
if(uf.same(a,b)){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
sntea |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2627 Byte |
Status |
AC |
Exec Time |
54 ms |
Memory |
2048 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 |
32 ms |
768 KB |
subtask_01_02.txt |
AC |
2 ms |
1408 KB |
subtask_01_03.txt |
AC |
47 ms |
1024 KB |
subtask_01_04.txt |
AC |
54 ms |
2048 KB |
subtask_01_05.txt |
AC |
5 ms |
256 KB |
subtask_01_06.txt |
AC |
6 ms |
1408 KB |
subtask_01_07.txt |
AC |
50 ms |
896 KB |
subtask_01_08.txt |
AC |
54 ms |
2048 KB |
subtask_01_09.txt |
AC |
1 ms |
256 KB |
subtask_01_10.txt |
AC |
2 ms |
1408 KB |
subtask_01_11.txt |
AC |
46 ms |
896 KB |
subtask_01_12.txt |
AC |
54 ms |
2048 KB |
subtask_01_13.txt |
AC |
42 ms |
768 KB |
subtask_01_14.txt |
AC |
2 ms |
1408 KB |
subtask_01_15.txt |
AC |
47 ms |
896 KB |
subtask_01_16.txt |
AC |
54 ms |
2048 KB |
subtask_01_17.txt |
AC |
51 ms |
1792 KB |
subtask_01_18.txt |
AC |
51 ms |
1792 KB |