Submission #1230219

#TimeUsernameProblemLanguageResultExecution timeMemory
1230219Tenis0206Drawing (CEOI22_drawing)C++20
15 / 100
1595 ms22660 KiB
#include <bits/stdc++.h> #define int long long 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]; point v[nmax + 5]; point aux[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, int cnt) { rez[r.poz] = nod; if(!st[nod]) { return; } sort(v + 1, v + cnt + 1, [r](point a, point b) { int 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 = v[cnt]; dfs(st[nod], r_st, cnt - 1); } else { point r_st = v[w[st[nod]]]; point r_dr = v[w[st[nod]] + 1]; dfs(st[nod], r_st, w[st[nod]] - 1); int nr = 0; for(int i=w[st[nod]]+2;i<=cnt;i++) { aux[++nr] = v[i]; } aux[++nr] = v[w[st[nod]] + 1]; aux[++nr] = v[w[st[nod]]]; for(int i=1;i<w[st[nod]];i++) { aux[++nr] = v[i]; } for(int i=1;i<=cnt;i++) { v[i] = aux[i]; } dfs(dr[nod], r_dr, w[dr[nod]] - 1); } } signed 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); } point r = point{0, -1, 0}; for(int i=1; i<=n; i++) { point p; cin>>p.x>>p.y; p.poz = i; v[i] = p; if(p.y > r.y) { r = p; } } int nr = 0; for(int i=1;i<=n;i++) { if(v[i].poz == r.poz) { continue; } aux[++nr] = v[i]; } for(int i=1;i<n;i++) { v[i] = aux[i]; } int root = 0; for(int i=1;i<=n;i++) { if(G[i].size() != 3) { root = i; break; } } get_sons(root); dfs(root, r, n - 1); 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...