Codeforces ECR #049 : F. Session in BSU

言われてみれば非常に単純。
http://codeforces.com/contest/1027/problem/F

問題

N種類の試験すべてを受験したい。
i番目の試験はA[i]日目かB[i]日目のいずれかに受験することができる。
1日には1つの試験しか受けられない。

全試験を受験することはできるか。可能なら全試験を受験し終わる最短日を答えよ。

解法

日を頂点とし、試験をA[i]とB[i]に対応する頂点を結ぶ辺とする。
試験のない日は無視すると、これは最大2N頂点、N辺をもつグラフとなる。

問題の条件を満たすには、各辺に対しどちらかの点を対応づけ、かつ各点は最大1辺にしか対応付けられないようにしたい。
また、点が余る場合は、後ろの日付が余るようにしたい。

以後各連結成分毎に考える。

• 辺の数が点より多い場合、全試験を受けることはできない。
• 辺の数が点と一致する場合、全試験日をフルに使い、全試験を受けることができる。その際、この連結成分に関する試験は、頂点のうち最も遅い日付に受験し終わる。
• 辺の数が点より1小さい、試験日を1つ余らせて全試験を受けることができる。その際、この連結成分に関する試験は、頂点のうち２番目に遅い日付に受験し終わる。

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<2500000> uf;

int N;
int A[1010101],B[1010101];
vector<int> V;
vector<ll> C[2010101];
int NE[2010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d%d",&A[i],&B[i]);
		V.push_back(A[i]);
		V.push_back(B[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(V),A[i])-V.begin();
		B[i]=lower_bound(ALL(V),B[i])-V.begin();
		uf(A[i],B[i]);
	}
	
	FOR(i,V.size()) C[uf[i]].push_back(V[i]);
	FOR(i,N) NE[uf[A[i]]]++;
	
	ll ma=0;
	FOR(i,V.size()) if(C[i].size()) {
		if(C[i].size()<NE[i]) return _P("-1\n");
		if(C[i].size()==NE[i]) ma=max(ma,C[i].back());
		if(C[i].size()==NE[i]+1) {
			C[i].pop_back();
			ma=max(ma,C[i].back());
		}
	}
	cout<<ma<<endl;
}

まとめ

本番二部グラフをどう扱うか悩んで時間切れしてしまった。