Codeforces #583 E. Petya and Construction Set

この回は不参加です。
https://codeforces.com/contest/1214/problem/E

問題

2N個の頂点からなず木を成す無向グラフが与えられる。
N個の頂点対(同じ頂点は1回ずつしか登場しない)における距離が与えられる。
なお、その距離はN以下である。

入力の距離を満たすグラフを構築せよ。

解法

まず各頂点対を距離の降順にし、対から1つずつ頂点を取り出してN個順に並べる。
再度頂点対を走査し、もう片方の頂点を追加していこう。

頂点の追加方法としては、列の末尾に追加するか、途中で枝分かれさせればよい。
もしi番目に追加するものが(i-1)番目に追加するのと同じ距離の対であれば、直前の頂点の後ろに追加すればよいし、そうでなければ途中で枝分かれさせて条件を満たすものが必ず存在する。

int N;
int D[101010];
pair<int,int> P[101010];
int num[202020];
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>D[i];
		P[i]={D[i],i};
	}
	sort(P,P+N);
	reverse(P,P+N);
	
	FOR(i,N) {
		num[i]=P[i].second*2+1;
		if(i) V.push_back({num[i],num[i-1]});
	}
	FOR(i,N) {
		if(num[i+P[i].first]==0) num[i+P[i].first]=P[i].second*2+2;
		V.push_back({P[i].second*2+2,num[i+P[i].first-1]});
	}
	
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
}

まとめ

距離がN以下ってのがコツ。