Submission #816891

#	Time	Username	Problem	Language	Result	Execution time	Memory
816891		enerelt14	Drawing (CEOI22_drawing)	C++14	100 / 100	300 ms	38468 KiB

Main

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define ff first
#define ss second

const int MX = 2e5 + 5;

int n, x[MX], y[MX], sub[MX];
int ord[MX], ans[MX];
vector<int> adj[MX];

void dfs(int u, int pre) {
	sub[u]++;
	for(int i = 0; i < adj[u].size(); i++) {
		if(adj[u][i] == pre) continue;
		dfs(adj[u][i], u);
		sub[u] += sub[adj[u][i]];
	}
}

void solve(int u, int pre, int cnt) {
	ans[ord[sub[u] + cnt - 1]] = u + 1;
	for(int i = 0; i < adj[u].size(); i++) {
		if(adj[u][i] == pre) continue;
		solve(adj[u][i], u, cnt);
		cnt += sub[adj[u][i]];
	}
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	dfs(0, 0);
	// if(n <= 10000) {
	// 	go();
	// 	return 0;
	// }
	vector<pair<double, int> > sl;
	int mn = INT_MAX;
	for(int i = 0; i < n; i++) {
		if(mn <= x[i]) continue;
		mn = x[i];
		ord[0] = i;
	}
	for(int i = 0; i < n; i++) {
		if(i == ord[0]) continue;
		sl.pb({(double)(y[i] - y[ord[0]]) / (double)(x[i] - x[ord[0]]), i});
	}
	sort(sl.begin(), sl.end());
	for(int i = 1; i < n; i++) {
		ord[i] = sl[i - 1].ss;
	}
	solve(0, 0, 0);
	for(int i = 0; i < n; i++) cout << ans[i] << " ";
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < adj[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void solve(int, int, int)':
Main.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < adj[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~

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