AtCoder ARC #036 : D - 偶数メートル

わかってしまえばとてもあっさり。
http://arc036.contest.atcoder.jp/tasks/arc036_d

問題

N頂点からなるグラフがある。ただし初期状態では辺はない。
以下のQ個のクエリを順次処理せよ。

1. 点x,yの間に距離zの無向辺を張る
2. 点xから点yまで、総移動距離が偶数となる移動方法があるか判定せよ。
   • 同じ点・辺を複数回通っても良い。

解法

Union-Findで解く。

N個の頂点から、Union-Find上で2N頂点を作る。
片方は偶数距離の頂点を結ぶためのもので、片方は奇数距離の頂点を結ぶものである。
例えば、i番の頂点からi*2番を偶数用、i*2+1番を奇数用とする。

• 1番のクエリが来た場合
  • zが偶数なら、2*xと2*y、2*x+1と2*y+1の点をuniteする。
  • zが奇数なら、2*xと2*y+1、2*xと2*y+1の点をuniteする。
• 2番のクエリが来た場合
  • 2*xと2*yがuniteされているかどうか判定する。

Union-Findライブラリを除くと、非常に単純。

class UF {
	public:
	int um;
	vector<int> ufpar,ufrank,ufcnt;
	UF(int um_=200005) { um=um_; ufrank=vector<int>(um,0); ufcnt=vector<int>(um,1); for(int i=0;i<um;i++) ufpar.push_back(i);}
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

UF uf;
int N,Q;

void solve() {
	int i,j,k,l,w,r,x,y,z; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>w>>x>>y>>z;
		if(w==1) {
			uf.unite(x*2,y*2+z&1);
			uf.unite(x*2+1,y*2+(1-z&1));
		}
		else {
			if(uf[x*2]==uf[y*2]) cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
	}
}

まとめ

本番は状態遷移が混乱して解ききれず…。
こんなあっさり解けるとは。