Submission #1219657

#TimeUsernameProblemLanguageResultExecution timeMemory
1219657MateiKing80Drawing (CEOI22_drawing)C++20
15 / 100
1600 ms337452 KiB
#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) { nth_element(points.begin(), points.begin(), points.end(), [&] (int a, int b) { if (a == loc || b == loc) return b != loc; return clockwise(puncte[loc], puncte[a], puncte[b]); }); nth_element(points.begin() + 1, points.begin() + 1, points.end(), [&] (int a, int b) { if (a == loc || b == loc) return b != loc; return clockwise(puncte[loc], puncte[a], puncte[b]); }); vector<int> npoints; for (int i = 1; i < points.size(); i ++) npoints.push_back(points[i]); solve(rvec[root][0], points[1], npoints); } else { nth_element(points.begin(), points.begin(), points.end(), [&] (int a, int b) { if (a == loc || b == loc) return b != loc; return clockwise(puncte[loc], puncte[a], puncte[b]); }); nth_element(points.begin() + 1, points.begin() + 1, points.end(), [&] (int a, int b) { if (a == loc || b == loc) return b != loc; return clockwise(puncte[loc], puncte[a], puncte[b]); }); nth_element(points.begin() + 2, points.begin() + 1 + sz[rvec[root][0]], points.end(), [&] (int a, int b) { if (a == loc || b == loc) return b != loc; 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() { 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); for (int i = 1; i <= n; i ++) cout << ans[i] << " "; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...