kmjp's blog

競技プログラミング参加記です

CODE THANKS FESTIVAL 2017 : H - Union Sets

これ系のテク自分で使ったの初めてだけど意外にすんなり書けた。
https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_h

問題

N個の頂点があり、M個の辺を順に追加していくことを考える。
ここでQ個のクエリが与えられる。
各クエリは2頂点対X,Yからなる。
X,Yが連結成分となるのは何本目の辺を追加したときか答えよ。

解法

並列二分探索で解く。
各クエリに対し、解の候補となる区間を初期状態として[1,M+1]と持たせて置く。
今解の候補が[L,R]であるなら、(L+R)/2本辺を追加を追加した時点で連結しているかどうかを持ってL,Rを更新しよう。

一回の探索で範囲を半分に狭められるので、Union-Findを用いてlog(M)回程度M個の辺追加をシミュレートすれば解を特定できる。

int N,M,Q;
int A[101010],B[101010];
int X[101010],Y[101010];
int L[101010],R[101010];
vector<int> cand[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		L[i]=1;
		R[i]=M+1;
	}
	
	FOR(i,20) {
		FOR(x,Q) cand[(L[x]+R[x])/2].push_back(x);
		FOR(x,N) uf.par[x]=x, uf.rank[x]=0;
		FOR(x,M) {
			uf(A[x],B[x]);
			FORR(e,cand[x+1]) {
				if(uf[X[e]]==uf[Y[e]]) {
					R[e]=x+1;
				}
				else {
					L[e]=x+2;
				}
			}
			cand[x+1].clear();
		}
	}
	
	FOR(i,Q) {
		if(L[i]>M) cout<<-1<<endl;
		else cout<<L[i]<<endl;
	}
	
}

まとめ

LCA解は思いつかなかった…。