Submission #3413141

---

Source Code Expand

#include <iostream>
using namespace std;
typedef long long ll;
int N,Q,x,y,z,w;
int p[200010] = {0},r[200010] = {0};

void init(int N){
	for(int i=0;i<=N;++i) p[i] = i;
}

int root(int a){
	if(p[a] == a) return a;
	return (p[a] = root(p[a]));
}

bool is_same_set(int a,int b){
	return root(a) == root(b);
}

void unite(int a, int b){
	a = root(a);
	b = root(b);
	if(a==b) return;
	if(r[a]<r[b]){
		p[a] = b;
	}else{
		p[b] = a;
		if(r[a] == r[b]) r[a]++;
	}
}

int main(){
	cin >> N >> Q;
	init(2*N);
	for(int i=0;i<Q;i++){
		cin >> w >> x >> y >> z;
		if(w==1){
			if(z%2==0){
				unite(x,y); unite(x+N,y+N);
			}else{
				unite(x,y+N); unite(x+N,y);
			}
		}else{
			cout << (is_same_set(x,y)? "YES":"NO") << endl;
		}
	}
}

Submission Info

Judge Result