TopCoderOpen 2017 Round2A Medium DistanceZeroAndOne

元のコードでなぜ落ちるかいまだによくわかっていない。
https://community.topcoder.com/stat?c=problem_statement&pm=14596

問題

連結無向グラフがあるとする。
各頂点vに対し、頂点0からの距離D0(v)と頂点1からの距離D1(v)が与えられる。
それらの条件を満たすグラフが存在するか。存在するなら1例を示せ。

解法

なんかこれの難しい版が既出だったらしい。
http://cf16-exhibition-open.contest.atcoder.jp/tasks/codefestival_2016_ex_a

以下の2条件を満たす2頂点v-v'間に辺を張り、最後に条件に反しないかWarshall-Floyedでチェックすればよい。

• abs(D0(v)-D0(v'))≦1
• abs(D1(v)-D1(v'))≦1

class DistanceZeroAndOne {
	public:
	int N;
	int mat[51][51];
	
	vector <string> construct(vector <int> D0, vector <int> D1) {
		vector<string> V,emp;
		int x,y,z;
		
		N=D0.size();
		FOR(x,N) V.push_back(string(N,'N'));
		FOR(x,N) FOR(y,N) {
			if(x==y) mat[x][y]=0;
			else {
				if(abs(D0[x]-D0[y])<=1 && abs(D1[x]-D1[y])<=1) mat[x][y]=1, V[x][y]='Y';
				else mat[x][y]=1010;
			}
		}
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
		FOR(x,N) if(mat[0][x]!=D0[x] || mat[1][x]!=D1[x]) return emp;
		
		
		
		return V;
		
	}
}

まとめ

似たようなのCodeforcesで解いたような気もするんだけどな。