2017 TCO Round2A 500 DistanceZeroAndOne

2017-05-21

11:38 |

頂点 0〜N-1 の無向連結グラフを作りたい。頂点0〜頂点iの最短距離はdist0[i], 頂点1〜頂点iの最短距離はdist1[i]でないといけない。
各辺の距離は 1. 作れるならその一例、作れなければ空を返せ。
2≦N≦50

(TCO出忘れたのであとで)

考察
連結なので頂点0からの距離が1の頂点は必ずある。
同じく頂点0からの距離が M なものがあったら dist0 には 1〜M が含まれる。

頂点0 から距離 1 の頂点は頂点0と必ず繋がっている必要がある。(頂点0は1個なので)
頂点0 から距離 2 の頂点は頂点0 から距離 1 の頂点のどれかと繋がっている必要がある。
頂点1からの距離制約があるので、全部繋げてよいとは限らない。
繋げていいやつだけ繋げてどれかと繋がったか判定すればよさそう
繋げていいかどうかは、繋げたとき頂点1の距離制約を破らなければよい。
u, v を繋げるとして、u, v の頂点1 からの距離の差の絶対値が2以上のときに繋げると頂点1からの距離の差が1になってしまうのでだめ
元々 1 以下のときはOKなので実際に繋げる
最後にできたグラフをWFしてdist0, dist1と矛盾ないかチェック (これやってなくてWA)

Accepted in practice

void add(vector<string>& w, int n0, int n1) {
	w[n0][n1] = w[n1][n0] = 'Y';
}

class DistanceZeroAndOne {
	public:
	vector <string> construct(vector <int> d0, vector <int> d1) {
		ll N = d0.size();
		if(!(d0[0]==0 && d0[1]==d1[0] && d1[1]==0)) return {};

		vector<string> g(N, string(N, 'N'));
		VVI n0(N), n1(N);
		REP(i, N) n0[d0[i]].PB(i);
		REP(i, N) n1[d1[i]].PB(i);
		RANGE(i, 1, N) {
			ll pi = i-1;
			for(int v2 : n0[i]) {
				bool any=false;
				for(int v1 : n0[pi]) {
					if(abs(d1[v1]-d1[v2]) < 2) {
						any=true;
						add(g, v1, v2);
					}
				}
				if(!any) return {};
			}
			for(int v2 : n1[i]) {
				bool any=false;
				for(int v1 : n1[pi]) {
					if(abs(d0[v1]-d0[v2]) < 2) {
						any=true;
						add(g, v1, v2);
					}
				}
				if(!any) return {};
			}
		}
		VVI w(N, VI(N, 1LL<<60));
		REP(i, N) REP(j, N) if(g[i][j]=='Y') w[i][j]=1;
		REP(i, N) w[i][i]=0;
		REP(k, N) REP(i, N) REP(j, N) w[i][j] = min(w[i][j], w[i][k]+w[k][j]);
		REP(i, N) if(d0[i]!=w[0][i]) return {};
		REP(i, N) if(d1[i]!=w[1][i]) return {};
		return g;
	}
};