Submission #1278559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278559		trideser	Drawing (CEOI22_drawing)	C++20	100 / 100	278 ms	25604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int ix = 0;
vector<bool> visited;
vector<vector<int>> edges;
vector<int> mapping;
vector<int> res;
void dfs(int node) {
	res[node] = ix++;
	visited[node] = true;
	for(int e : edges[node]) {
		if(visited[e]) continue;
		visited[e] = true;
		dfs(e);
	}
}

int main() {
	int N;
	cin >> N;
	edges = vector<vector<int>>(N, vector<int>());
	res = vector<int>(N);
	visited = vector<bool>(N, false);
	for(int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	vector<tuple<int, int, int>> polygon;
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		polygon.push_back(make_tuple(a, b, i));
	}
	sort(polygon.begin(), polygon.end());
	mapping = vector<int>(N);
	int ix = 0;
	int x0 = get<0>(polygon[0]);
	int y0 = get<1>(polygon[0]);
	int x1 = get<0>(polygon.back());
	int y1 = get<1>(polygon.back());

	for(int i = 0; i < N; i++) {
		int x, y, ii;
		tie(x, y, ii) = polygon[i];
		if((x - x0) * (y1 - y0) <= (x1 - x0) * (y - y0)){
			mapping[ix++] = ii;
		}
	}
	for(int i = N - 1; i >= 0; i--) {
		int x, y, ii;
		tie(x, y, ii) = polygon[i];
		if((x - x0) * (y1 - y0) > (x1 - x0) * (y - y0)){
			mapping[ix++] = ii;
		}
	}
	dfs(0);
	for(int a : res) cout << a + 1 << "\n";

	return 0;
}

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