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;
}