Codeforces #237 Div2 C. Restore Graph

CF#237に参加。Div2 Only回なので気が楽だね。
せっかくDEも解けたのに、BCをオーバーフローで落としてしまい残念。
http://codeforces.com/contest/404/problem/C

問題

N点で構成される連結グラフがある。
各点は最大K辺までつながることができる。
各辺のコストを1とみなしたとき、ある点から各点へのコストD[i]が与えられる。
条件を満たすグラフが作成可能であれば、それを返せ。

解法

まず、D[i]==0となる点が1つだけなければならない。
あとはD[i]==Pとなる点に対しD[j]==P+1となる点を最大K点までつなげていき、木を作ればよい。

ll K,N;
int D[100002],EE[100002];
vector<int> DS[100002];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>D[i];
		DS[D[i]].push_back(i);
	}
	
	int tot=1;
	if(DS[0].size()!=1) return _P("-1\n");
	FOR(i,N) {
		
		if(i==0 && DS[i+1].size()>DS[i].size()*(K)) return _P("-1\n");
		if(i>0 && DS[i+1].size()>DS[i].size()*(K-1)) return _P("-1\n");
		tot+=DS[i+1].size();
	}
	if(tot!=N) return _P("-1\n");
	_P("%d\n",N-1);
	
	int prev_in=0;
	int ne=0;
	FOR(i,N) {
		prev_in=0;
		ne=0;
		FOR(j,DS[i+1].size()) {
			ne++;
			if(i==0 && ne>K) prev_in++,ne=1;
			if(i>0 && ne>K-1) prev_in++,ne=1;
			_P("%d %d\n",DS[i][prev_in]+1,DS[i+1][j]+1);
		}
	}
}

まとめ

本番オーバーフローで落としてしまい残念…。