AtCoder AGC #002 : D - Stamp Rally

ゴリ押しで通してしまった。
http://agc002.contest.atcoder.jp/tasks/agc002_d

問題

N頂点M辺からなる無向グラフがある。
各辺は1～Mの番号が振られている。

このグラフに対し、以下のクエリQ個を答えよ。
各クエリは２つの異なる頂点(X,Y)と整数Zからなる。
i番以下の辺だけを用いて、X,Yから到達可能な頂点がZ個以上になる最小のiを答えよ。

解法

辺を1個ずつ追加していくたびにUnion-Findで(X,Y)から到達可能な頂点数を求めれば、一応解にはたどり着く。
ただしこの場合計算量がO(MQα)であり間に合わない。

自分が本番通したときは平方分割で行った。
辺を追加するたびに毎回各クエリの判定をするのは重いので、まず１周辺を追加し、√M回ごとに各クエリに対し頂点数がZ個を超えるか判定する。
これにより各クエリはどの√M回のうちに条件を満たすかが大ざっぱにわかる。
次に再度辺を追加する処理を行い、今回は各クエリが条件を満たす√M回の範囲だけ厳密に解をチェックする。
こうするとO(√MQα)で、1.98sと(若干の定数倍高速化も含めれば)ギリギリ間に合う。

想定解は並列で二分探索を行うこと。
初期状態では、全部の辺を使うこと、すなわち各クエリの解がMだとする。
ここでA=log2(M)回程度辺の追加処理を繰り返す。
j回目のループでは、今より2^(A-1-j)番少ない辺まで追加した時点で条件を満たせるかどうかを判定していく。
こちらはO(logM*(M+Q)*α)で済み0.7s程度で解ける。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<101010> uf;

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,M) scanf("%d%d",&A[i],&B[i]);
	
	scanf("%d",&Q);
	FOR(i,Q) scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
	FOR(i,Q) cand[18][M-1].push_back(i);
	
	for(j=17;j>=0;j--) {
		uf.reinit();
		
		FOR(i,M) {
			x=i+(1<<j);
			uf(A[i],B[i]);
			FORR(r,cand[j+1][x]) {
				if(uf.count(X[r])+((uf[X[r]]==uf[Y[r]])?0:uf.count(Y[r]))>=Z[r]) cand[j][i].push_back(r);
				else cand[j][x].push_back(r);
			}
			if(i<1<<j) {
				FORR(r,cand[j+1][i]) cand[j][i].push_back(r);
			}
		}
	}
	FOR(i,M) FORR(r,cand[0][i]) R[r]=i+1;
	FOR(i,Q) _P("%d\n",R[i]);
}

まとめ

まぁ平方分割は時間ぎりぎりすぎて想定解じゃないだろうなとは思ったけどさ。