## #2327565

Solution for DSL_1_A: Disjoint Set: Union Find Tree by wk

Source Code Status Test Cases
Policy: public     Reviewed: 22
00.06 sec    3784 KB    82 lines     1687 bytes    2017-05-20 02:59
```#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
os << "[";
for (const auto &v : vec) {
os << v << ",";
}
os << "]";
return os;
}

using i64=int64_t;

class quick_find_weighted{
public:
int size=0;
vector<int> belong;
vector<set<int>> groups;
quick_find_weighted(int size_):size(size_),belong(size_),groups(size_){
for(int i=0; i<size; ++i){
belong[i]=i;
groups[i].insert(i);
}
}
void unite(int x,int y){
int gx=belong[x],gy=belong[y];
if(gx==gy) return;
if(groups[gx].size()<groups[gy].size()) swap(gx,gy);
for(int z:groups[gy]) belong[z]=gx;
groups[gx].insert(groups[gy].begin(),groups[gy].end());
groups[gy].clear();
}
int find(int x)const{
return belong[x];
}
bool is_same_group(int x,int y)const{
return find(x)==find(y);
}
void erase(int x){
int gx=belong[x];
if(gx==-1) return;
belong[x]=-1;
groups[gx].erase(x);
}
};

void solve(){
int n,q;
cin >> n >> q;
quick_find_weighted ds(n);
rep(i,0,q){
int com,x,y;
cin >> com >> x >> y;
if(com==0) ds.unite(x,y);
else cout << int(ds.is_same_group(x,y)) << endl;
}
}

int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(10);
solve();
return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 32/32 C++14 CPU: 00.06 sec Memory: 3784 KB Length: 1687 B 2017-05-20 02:59 2017-05-20 02:59
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 3112 KB Case #2: : Accepted 00.00 sec 3108 KB Case #3: : Accepted 00.00 sec 3192 KB Case #4: : Accepted 00.00 sec 3104 KB Case #5: : Accepted 00.00 sec 3068 KB Case #6: : Accepted 00.00 sec 3120 KB Case #7: : Accepted 00.00 sec 3056 KB Case #8: : Accepted 00.00 sec 3196 KB Case #9: : Accepted 00.00 sec 3004 KB Case #10: : Accepted 00.00 sec 3172 KB Case #11: : Accepted 00.00 sec 3364 KB Case #12: : Accepted 00.00 sec 3740 KB Case #13: : Accepted 00.00 sec 3116 KB Case #14: : Accepted 00.00 sec 3032 KB Case #15: : Accepted 00.00 sec 3036 KB Case #16: : Accepted 00.00 sec 3024 KB Case #17: : Accepted 00.00 sec 3200 KB Case #18: : Accepted 00.00 sec 3152 KB Case #19: : Accepted 00.00 sec 3224 KB Case #20: : Accepted 00.00 sec 3440 KB Case #21: : Accepted 00.00 sec 3728 KB Case #22: : Accepted 00.01 sec 3748 KB Case #23: : Accepted 00.01 sec 3732 KB Case #24: : Accepted 00.01 sec 3744 KB Case #25: : Accepted 00.02 sec 3692 KB Case #26: : Accepted 00.02 sec 3656 KB Case #27: : Accepted 00.02 sec 3740 KB Case #28: : Accepted 00.01 sec 3780 KB Case #29: : Accepted 00.00 sec 3732 KB Case #30: : Accepted 00.04 sec 3784 KB Case #31: : Accepted 00.04 sec 3692 KB Case #32: : Accepted 00.06 sec 3692 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )