Submission #742890

#	Time	Username	Problem	Language	Result	Execution time	Memory
742890		hmm789	Drawing (CEOI22_drawing)	C++14	100 / 100	219 ms	36964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> adj[200000];
vector<int> topo;

void dfs(int x, int p) {
	for(int i : adj[x]) if(i != p) {
		dfs(i, x);
	}
	topo.push_back(x);
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, x, y;
	cin >> n;
	for(int i = 0; i < n-1; i++) {
		cin >> x >> y;
		x--; y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs(0, -1);
	reverse(topo.begin(), topo.end());
	pair<pair<int, int>, int> pt[n];
	int ans[n];
	for(int i = 0; i < n; i++) {
		cin >> pt[i].first.first >> pt[i].first.second;
		pt[i].second = i;
	}
	sort(pt, pt+n);
	vector<pair<pair<int, int>, int>> top, bottom;
	top.push_back(pt[0]);
	bottom.push_back(pt[0]);
	int idx = -1;
	for(int i = 1; i < n; i++) {
		if(pt[i].first.second < bottom.back().first.second) bottom.push_back(pt[i]);
		else if(pt[i].first.second > top.back().first.second) top.push_back(pt[i]);
		else {
			idx = i;
			break;
		}
	}
	for(int i = idx; i < n; i++) {
		if(abs(pt[i].first.second-bottom.back().first.second) < abs(pt[i].first.second-top.back().first.second)) bottom.push_back(pt[i]);
		else top.push_back(pt[i]);
	}
	for(int i = 0; i < n; i++) {
		if(i < top.size()) {
			ans[top[i].second] = topo[i];
		} else {
			ans[bottom[bottom.size()-1-(i-top.size())].second] = topo[i];
		}
	}
	for(int i = 0; i < n; i++) cout << ans[i]+1 << " ";
}
	

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:52:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if(i < top.size()) {
      |      ~~^~~~~~~~~~~~

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