Submission #2171205

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))

#include <vector>
using namespace std;


struct UnionFind
{
	vector<int> par_;
	vector<int> rank_;

	void init(int size)
	{
		par_.resize(size, 0);
		rank_.resize(size, 0);
		for (int i = 0; i < size; i++)
		{
			par_[i] = i;
			rank_[i] = 0;
		}
	}
	int root(int x)
	{
		return par_[x] == x ? x : par_[x] = root(par_[x]);
	}

	bool unite(int x, int y)
	{
		x = root(x);
		y = root(y);
		if (x == y)
			return true;

		if (rank_[x] < rank_[y])
		{
			par_[x] = y;
		}
		else
		{
			par_[y] = x;
			if (rank_[x] == rank_[y])
				rank_[x]++;
		}
		return false;
	}
	bool same(int x, int y)
	{
		return root(x) == root(y);
	}
};

int main()
{
	int n,q;
	cin >> n >> q;
	UnionFind uf;
	uf.init(n * 2 + 5);

	for(int i = 0;i < q;i++)
	{
		int w,x,y,z;
		cin >> w >> x >> y >> z;
		if(w == 1)
		{
			if(z % 2 == 0)
			{
				uf.unite(x , y);
				uf.unite(x + n , y + n);
			}
			else
			{
				uf.unite(x + n , y);
				uf.unite(x , y + n);
			}
		}
		else
		{
			if(uf.same(x,y))
			{
				cout << "YES" << endl;
			}
			else{
				cout << "NO" << endl;
			}
		}
	}
}

Submission Info

Judge Result