Submission #1219676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219676		MateiKing80	Drawing (CEOI22_drawing)	C++20	30 / 100	1489 ms	589824 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

struct Point {
	int x, y;
} puncte[N];

int area(Point a, Point b, Point c) {
	return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x) / 2;
}

bool clockwise(Point a, Point b, Point c) {
	return area(a, b, c) > 0;
}

vector<int> vec[N];
vector<int> rvec[N];
int sz[N], ans[N];

void dfsz(int nod, int papa) {
	sz[nod] = 1;
	for (auto i : vec[nod])
		if (i != papa) {
			dfsz(i, nod);
			sz[nod] += sz[i];
			rvec[nod].push_back(i);
		}
}

void solve(int root, int loc, vector<int> points) {
	ans[loc] = root;
	if (rvec[root].size() == 0) {
		return;
	} else if (rvec[root].size() == 1) {
		for (int i = 1; i < points.size(); i ++)
			if (points[i] == loc)
				swap(points[0], points[i]);
		int mn = 1;
		for (int i = 2; i < points.size(); i ++)
			if (clockwise(puncte[loc], puncte[points[i]], puncte[points[mn]]))
				mn = i;
		swap(points[1], points[mn]);
		vector<int> npoints;
		for (int i = 1; i < points.size(); i ++)
			npoints.push_back(points[i]);
		solve(rvec[root][0], points[1], npoints);
	} else {
		for (int i = 1; i < points.size(); i ++)
			if (points[i] == loc)
				swap(points[0], points[i]);
		int mn = 1;
		for (int i = 2; i < points.size(); i ++)
			if (clockwise(puncte[loc], puncte[points[i]], puncte[points[mn]]))
				mn = i;
		swap(points[1], points[mn]);
		nth_element(points.begin() + 2, points.begin() + 1 + sz[rvec[root][0]], points.end(), [&] (int a, int b) {
			return clockwise(puncte[loc], puncte[a], puncte[b]);
		});
		vector<int> npoints1;
		for (int i = 1; i <= sz[rvec[root][0]]; i ++)
			npoints1.push_back(points[i]);
		vector<int> npoints2;
		for (int i = sz[rvec[root][0]] + 1; i < points.size(); i ++)
			npoints2.push_back(points[i]);
		solve(rvec[root][0], points[1], npoints1);
		solve(rvec[root][1], points[sz[rvec[root][0]] + 1], npoints2);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;
	if (n == 1) {
		cout << "1\n";
		return 0;
	}
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int root = 0;
	for (int i = 1; i <= n; i ++)
		if ((int)vec[i].size() == 1)
			root = i;
	vector<int> nodes;
	for (int i = 1; i <= n; i ++) {
		cin >> puncte[i].x >> puncte[i].y;
		nodes.push_back(i);
	}
	dfsz(root, 0);
	int xmin = 1e9 + 1, loc = 0;
	for (int i = 1; i <= n; i ++)
		if (puncte[i].x < xmin) {
			xmin = puncte[i].x;
			loc = i;
		}
	solve(root, loc, nodes); //trebuie un loc
	for (int i = 1; i <= n; i ++)
		cout << ans[i] << " ";
	cout << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 35
• Subtask 5: 0 / 25