#2327565

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

Source Code Status Test Cases
    Policy: public     Reviewed: 14    
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 #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags