Codeforces #360 Div1 D. Dividing Kingdom II

これ本番解けば良かった。
http://codeforces.com/contest/687/problem/D

問題

N頂点M辺のグラフがある。
各辺の長さはW[i]である。
この状態でQ個のクエリに答えよ。

各クエリは辺の番号の対(L,R)で与えられる。
元グラフのうちこの番号の範囲内に含まれる辺だけで構成された部分グラフを考える。
頂点を２つの集合に分けるとき、同じ集合に分類される頂点間の辺の長さの最大値を最小化したい。
最適に集合を分けたとき、上記長さの最大値を答えよ。

解法

クエリ内の処理がややこしいが、要は辺を長い順に加えていき、始めて二部グラフにならないような辺があれば、その長さを答えればよい。
最初に全部の辺をW[i]降順にソートしておくと、全体でO(QMα)で余り工夫なく通る。
とはいえ割と時間はシビアなので、余計なことはしないよう注意しよう。

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;
	}
};
int N,M,Q;
int U[1010101],V[1010101],W[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<int,int>> P;
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		P.push_back({W[i],i});
	}
	sort(ALL(P));
	reverse(ALL(P));
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--,R--;
		UF<2002> uf;
		int ret=-1;
		FORR(r,P) {
			x=r.second;
			if(x<L || R<x) continue;
			if(uf[2*U[x]]==uf[2*V[x]+1]) continue;
			uf(2*U[x],2*V[x]+1);
			uf(2*U[x]+1,2*V[x]);
			if(uf[2*U[x]]==uf[2*U[x]+1]) {
				ret=W[x];
				break;
			}
		}
		cout<<ret<<endl;
		
	}
	
}

まとめ

本番O(QMα)では無理だろうと思って諦めてしまった…もったいない。