Submission #1153223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153223		Issa	Drawing (CEOI22_drawing)	C++20	30 / 100	1595 ms	17548 KiB

Main

// #include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 5e5 + 100;
const ll INF = (ll)4e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;

int n;
vector<int> g[maxn];
int used[maxn];
int x[maxn];
int y[maxn];
int f[maxn];
int p[maxn];

bool ok(pair<bool, pll> a, pair<bool, pll> b){
	if(a.first < b.first) return 0;
	if(a.first > b.first) return 1;
	if(a.second.first * b.second.second > b.second.first * a.second.second) return 1;
	return 0;
}

pair<bool, pll> get(int i, int j, bool c){
	if(c){
		if(x[j] >= x[i]){
			return {0, {y[j] - y[i], x[j] - x[i]}};
		} else{
			return {1, {y[j] - y[i], x[j] - x[i]}};
		}
	} else{
		if(x[j] <= x[i]){
			return {0, {y[j] - y[i], x[j] - x[i]}};
		} else{
			return {1, {y[j] - y[i], x[j] - x[i]}};
		}
	}
}

void dfs(int v, int p){
	used[f[v]] = 1;	
	for(int to: g[v]){
		if(to == p) continue;
		bool c = pii{x[f[p]], y[f[p]]} < pii{x[f[v]], y[f[v]]};
		for(int i = 1; i <= n; i++){
			if(used[i]) continue;
			if(!f[to] || ok(get(f[v], f[to], c), get(f[v], i, c))){
				f[to] = i;
			}
		}
		dfs(to, v);
	}
}

void test(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int mx = 0;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];
		if(!mx || pii{y[mx], x[mx]} < pii{y[i], x[i]}) mx = i;
	}
	x[0] = inf; y[0] = y[mx];
	f[1] = mx;
	dfs(1, 0);
	for(int i = 1; i <= n; i++){
		p[f[i]] = i;
	} for(int i = 1; i <= n; i++){
		cout << p[i] << ' ';
	} cout << ent;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1; 
    while(t--) test();
    cout << ent;
}

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