Google Code Jam 2020 Round 2 : B. Security Update

これは割とすんなり。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9/000000000033871f

問題

N頂点M辺のグラフが与えられる。
各辺は正整数の長さを持つものとする。

各頂点に対し、頂点1からの最短距離が与えられる。
ただし一部の点は、具体的な値でなく、自身より短い距離を持つ頂点数が示される。
条件を満たす辺の長さを求めよ。

解法

距離は2000以下なので、具体的な距離がわからない点はO(N^2)かけて求めてもよいし、O(max(D))やO(NlogN)でも行ける。
全点vの頂点1からの最短距離D[v]がわかれば、u-v間の辺の距離はmax(1,abs(D[u]-D[v]))にしておけばよい。

int C,D;
int X[1010];
vector<pair<int,int>> E[101];
int R[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>C>>D;
	vector<int> num[101];
	int pat[2020]={};
	for(i=1;i<C;i++) {
		cin>>X[i];
		if(X[i]>0) pat[X[i]]++;
		else num[-X[i]].push_back(i);
	}
	
	int cur=1;
	for(int t=1;t<=2010;t++) {
		FORR(a,num[cur]) {
			X[a]=t;
			pat[t]++;
		}
		num[cur].clear();
		cur+=pat[t];
	}
	
	FOR(i,C) E[i].clear();
	_P("Case #%d:",_loop);
	FOR(i,D) {
		cin>>x>>y;
		_P(" %d",max(1,abs(X[x-1]-X[y-1])));
	}
	_P("\n");
}

まとめ

長さを0にしてしまい1WA…。