ボーナス問題でした。
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; }
まとめ
これは即答できた。