kmjp's blog

競技プログラミング参加記です

Codeforces #394 Div2 E. Dasha and Puzzle

ボーナス問題でした。
http://codeforces.com/contest/761/problem/E

問題

N頂点の木を成すグラフが与えられる。
このグラフを二次元座標上に描画したい。
以下の条件を満たす配置が可能なら、それを示せ。

  • 各頂点は異なる格子点上に配置される。
  • 頂点を結ぶ辺は、軸に平行な線分で表現される。
  • 辺同士は端点以外では交差しない。

解法

当然次数5以上の頂点があれば、条件を満たす描画はできない。

あとは実は既出である。
座標の値の制限が緩い分、座標圧縮の手順は不要。
天下一プログラマーコンテスト2016 予選A : D - グラフィカルグラフ - kmjp's blog

int N;
vector<int> E[31];
ll X[101],Y[101];
ll dx[4]={1,-1,0,0};
ll dy[4]={0,0,1,-1};

void dfs(int cur,int pre,int NG,ll dis) {
	int ok=15;
	if(NG>=0) ok ^= 1<<NG;
	FORR(e,E[cur]) if(e!=pre) {
		int dir;
		FOR(dir,4) if(ok & (1<<dir)) {
			ok ^= (1<<dir);
			X[e]=X[cur]+dis*dx[dir];
			Y[e]=Y[cur]+dis*dy[dir];
			dfs(e,cur,dir^1,dis/2);
			break;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) if(E[i].size()>4) return _P("NO\n");
	dfs(0,-1,-1,1LL<<40);
	cout<<"YES"<<endl;
	FOR(i,N) cout<<X[i]<<" "<<Y[i]<<endl;
}

まとめ

これは即答できた。