Codeforces ECR #111 : F. Jumping Around

たまに出てくるなこれ。
https://codeforces.com/contest/1550/problem/F

問題

池にN個の石が並んで浮いており、それぞれの座標が与えられる。
カエルは初期状態でS番目の石の上におり、パラメータDを持つ。
以下のクエリに順次答えよ。

• パラメータKと石番号Iが与えられる。カエルは、距離(D-K)以上(D+K)以下にある石にジャンプできる場合、ジャンプを繰り返してS番の石からI番の石に移動できるかを求めよ。

解法

小さいKで達成できれば、大きいKで達成できるのは明らか。
よって、Kに関しMSTを求めることにしよう。
クラスカル法やプリム法では計算量が間に合わないので、ブルーフカ法を使って連結成分を広げて行くと良い。

int N,Q,F,D;
int A[1010101];
int V[1010101];
int ret[1202020];
vector<pair<int,int>> query[1010101];
vector<pair<int,int>> E[1010101];
set<int> S[1201010],As;

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,uf2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>F>>D;
	F--;
	MINUS(V);
	set<int> As;
	FOR(i,N) {
		cin>>A[i];
		V[A[i]]=i;
		As.insert(A[i]);
		S[i].insert(i);
	}
	FOR(i,Q) {
		cin>>x>>y;
		query[y].push_back({x-1,i});
	}
	
	while(1) {
		FOR(i,N) if(S[i].size()==N) break;
		if(i<N) break;
		vector<vector<int>> cand;
		FOR(i,N) if(S[i].size()) {
			FORR(s,S[i]) As.erase(A[s]);
			int mi=1<<30;
			int tar=0;
			FORR(s,S[i]) {
				auto it=As.lower_bound(A[s]+D);
				if(it!=As.end()&&*it-(A[s]+D)<mi) mi=*it-(A[s]+D),x=s,tar=V[*it];
				if(it!=As.begin()&&(A[s]+D)-*prev(it)<mi) mi=(A[s]+D)-*prev(it),x=s,tar=V[*prev(it)];
				
				it=As.lower_bound(A[s]-D);
				if(it!=As.end()&&*it-(A[s]-D)<mi) mi=*it-(A[s]-D),x=s,tar=V[*it];
				if(it!=As.begin()&&(A[s]-D)-*prev(it)<mi) mi=(A[s]-D)-*prev(it),x=s,tar=V[*prev(it)];
			}
			cand.push_back({min(x,tar),max(x,tar),mi});
			FORR(s,S[i]) As.insert(A[s]);
		}
		FORR(c,cand) {
			x=uf[c[0]];
			y=uf[c[1]];
			if(x!=y) {
				k=uf(x,y);
				l=x+y-k;
				E[c[2]].push_back({c[0],c[1]});
				if(S[k].size()<S[l].size()) swap(S[k],S[l]);
				FORR(s,S[l]) S[k].insert(s);
				S[l].clear();
			}
		}
		
	}
	
	FOR(i,1010001) {
		FORR2(x,y,E[i]) uf2(x,y);
		FORR2(v,t,query[i]) ret[t]=uf2[F]==uf2[v];
	}
	
	
	FOR(i,Q) {
		if(ret[i]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

まとめ

ブルーフカ法、稀に出てくるけどどういうときに向いてるのかさっと出てこないな…。