Codeforces Round #124 (Div. 1) C : Paint Tree
問題概要
ノード数N(<1500)の木が与えられる。二次元平面上にN個の点(どの3つも同一直線上にない)があるので、頂点を適当に割り振って平面グラフにする問題。
解法
木を適当に根を選んで根付き木にする。その後適当に1点選んで、それ以外の点を角度でソートして各部分木のサイズごとに再帰的に割り振る。
acceptされたコード
角度でソートするのが重くてTLEしたので、その部分だけ高速化している。
const int MAX_N = 1500; int N; vector< pair<Point, int> > ps; pair<Point,int> tp[MAX_N]; vector<int> graph_sub[MAX_N], graph[MAX_N]; int sz[MAX_N]; bool visited[MAX_N]; int ans[MAX_N]; double angles[MAX_N]; int ids[MAX_N], inv[MAX_N]; Point cur; void init(){ scanf("%d", &N); for(int i=0; i<N-1; ++i){ int x, y; scanf("%d%d", &x, &y); --x; --y; graph_sub[x].push_back(y); graph_sub[y].push_back(x); } for(int i=0; i<N; ++i){ int x, y; scanf("%d%d", &x, &y); ps.push_back( make_pair(Point(x, y), i) ); } sort(ps.begin(), ps.end()); } void dfs(int v){ visited[v] = true; for(int i=0; i<(int)graph_sub[v].size(); ++i){ const int u = graph_sub[v][i]; if(!visited[u]){ graph[v].push_back(u); dfs(u); sz[v] += sz[u]; } } ++sz[v]; } bool func (const pair<Point,int>& lhs, const pair<Point,int>& rhs){ return arg(lhs.first) < arg(rhs.first); } bool func2 (const pair<Point,int>& lhs, const pair<Point,int>& rhs){ return cmp_y(lhs.first, rhs.first); } bool func3 (const int& lhs, const int& rhs){ return angles[lhs] < angles[rhs]; } void rec(int v, int from, int to){ ans[ps[from].second] = v; if(to - from == 1){ return ; } for(int i=from+1; i<to; ++i){ angles[i] = arg(ps[i].first); ids[i] = i; } sort(ids + from + 1, ids + to, func3); for(int i=from+1; i<to; ++i){ tp[i] = ps[ids[i]]; } for(int i=from+1; i<to; ++i){ ps[i] = tp[i]; } //sort(ps.begin() + from + 1, ps.begin() + to, func); int p = from + 1; for(int i=0; i<(int)graph[v].size(); ++i){ const int u = graph[v][i]; double angle = arg(ps[p].first); for(int j=0; j<sz[u]; ++j){ ps[p+j].first = rot(ps[p+j].first, -angle); } for(int j=sz[u]-1; j>=0; --j){ ps[p+j].first -= ps[p].first; } rec(u, p, p + sz[u]); p += sz[u]; } } void solve(){ dfs(0); sort(ps.begin(), ps.end(), func2); for(int i=N-1; i>=0; --i){ ps[i].first -= ps[0].first; } rec(0, 0, N); for(int i=0; i<N; ++i){ printf("%d%c", ans[i] + 1, i==N-1?'\n':' '); } } int main(){ init(); solve(); return 0; }