Codeforces #335 Div1 B. Lazy Student

こっちもPretestでだいぶミスした。
http://codeforces.com/contest/605/problem/B

問題

N頂点M辺からなるグラフを考える。
M個の辺に関して、両端の点は不明だが、長さと最小全域木の構成辺になっているかが与えられる。

指定された辺が最小全域木を成すようなグラフを作成せよ。

解法

最小全域木の構成辺ではない長さの短い辺を配置するには、頂点間の距離ができるだけ短い方が良い。
よって、まず最小全域木を成す辺を1点に接続しよう。
例えば1番の頂点と、2～N番の頂点をそれぞれ最小全域木を成す辺のうち短い順に割り当てよう。

2～N番の頂点対(a,b)（a＜b）の間に、最小全域木を更新しないような辺を張れる条件は、新たに張る辺の長さが(1,b)の距離以上であることである。
この条件をもとに、最小全域木を構成しない辺について、短い順に頂点対(a,b)の間に振っていけば良い。
(a,b)の全頂点対をメモリで保持するとO(N^2)かかってしまうので、各aに対し、未使用で最小のbを管理すると良い。
例えば(a,b)に辺を張った場合、その時点で(a,b+1)を利用可能な辺候補に追加する。

何処に張っても最小全域木を更新してしまう場合は解無し。

int N,M;
vector<pair<int,int> > A;
vector<pair<int,int> > B;
int R[2][202020];
int C[101010],ne[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		if(y==0) B.push_back({x,i});
		else A.push_back({x,i});
	}
	sort(ALL(A));
	sort(ALL(B));
	
	priority_queue<pair<int,int> > PQ;
	FOR(i,N-1) {
		R[0][A[i].second]=0;
		R[1][A[i].second]=1+i;
		C[i+1]=A[i].first;
		ne[i+1]=i+2;
	}
	FOR(i,N-1) if(ne[i+1]<N) PQ.push({-C[ne[i+1]],i+1});
	
	FOR(i,B.size()) {
		auto r=PQ.top();
		PQ.pop();
		if(-r.first>B[i].first) return _P("-1\n");
		R[0][B[i].second] = r.second;
		R[1][B[i].second] = ne[r.second];
		ne[r.second]++;
		if(ne[r.second]<N) PQ.push({-C[ne[r.second]],r.second});
	}
	
	FOR(i,M) _P("%d %d\n",R[0][i]+1,R[1][i]+1);
}

まとめ

最初1列に辺を並べてしまって失敗した。