Submission #1230197

#TimeUsernameProblemLanguageResultExecution timeMemory
1230197Tenis0206Drawing (CEOI22_drawing)C++20
0 / 100
75 ms24864 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 2e5; struct point { int x, y, poz; }; int n; vector<int> G[nmax + 5]; int w[nmax + 5]; int st[nmax + 5], dr[nmax + 5]; int rez[nmax + 5]; void get_sons(int nod, int dad = 0) { w[nod] = 1; for(auto it : G[nod]) { if(it == dad) { continue; } if(!st[nod]) { st[nod] = it; } else { dr[nod] = it; } get_sons(it, nod); w[nod] += w[it]; } } void dfs(int nod, point r, vector<point> l) { rez[r.poz] = nod; if(!st[nod]) { return; } sort(l.begin(), l.end(), [r](point a, point b) { long long d = (1LL * a.x * r.y + 1LL * r.x * b.y + 1LL * b.x * a.y) - (1LL * a.y * r.x + 1LL * r.y * b.x + 1LL * b.y * a.x); return (d > 0); }); if(!dr[nod]) { point r_st = l.front(); vector<point> l_st; for(int i=1;i<l.size();i++) { l_st.push_back(l[i]); } dfs(st[nod], r_st, l_st); } else { point r_st = l[w[st[nod]] - 1]; point r_dr = l[w[st[nod]]]; vector<point> l_st, l_dr; for(int i=0;i<w[st[nod]]-1;i++) { l_st.push_back(l[i]); } for(int i=w[st[nod]]+1;i<l.size();i++) { l_dr.push_back(l[i]); } dfs(st[nod], r_st, l_st); dfs(dr[nod], r_dr, l_dr); } } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n; for(int i=1; i<n; i++) { int x, y; cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } vector<point> v; point r = point{0, -1, 0}; for(int i=1; i<=n; i++) { point p; cin>>p.x>>p.y; p.poz = i; v.push_back(p); if(p.y > r.y) { r = p; } } vector<point> aux; for(auto it : v) { if(it.poz == r.poz) { continue; } aux.push_back(it); } v = aux; get_sons(1); dfs(1, r, v); for(int i=1;i<=n;i++) { cout<<rez[i]<<' '; } return 0; }
#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...