Submission #1189928

#TimeUsernameProblemLanguageResultExecution timeMemory
1189928GrayDrawing (CEOI22_drawing)C++20
100 / 100
137 ms34404 KiB
#include <bits/stdc++.h> #include <cmath> using namespace std; #define ll int #define ull unsigned long long #define ld long double #define ff first #define ss second #define ln "\n" #define mp make_pair #define pb push_back #define INF (ll)1e18 ll MOD = (ll)(1e9+7); ll n; vector<array<ll, 3>> pts; vector<vector<ll>> A; vector<ll> sz; void dfs(ll u, ll p){ sz[u]=1; for (auto v:A[u]){ if (v==p) continue; dfs(v, u); sz[u]+=sz[v]; } } void gen(ll u, ll p, ll cx, ll cy, vector<array<ll, 3>> &avail, vector<ll> &res){ ll cnt=0; for (auto v:A[u]){ if (v==p) continue; cnt++; } if (false){ sort(avail.begin(), avail.end(), [&](auto &op1, auto &op2){ return atan2(op1[0]-cx, op1[1]-cy)<atan2(op2[0]-cx, op2[1]-cy); }); vector<array<ll, 3>> push; for (auto v:A[u]){ if (v==p) continue; push.clear(); ll ax=avail.back()[0], ay=avail.back()[1]; res[avail.back()[2]]=v; avail.pop_back(); for (ll i=0; i<sz[v]-1; i++) { push.push_back(avail.back()); avail.pop_back(); } gen(v, u, ax, ay, push, res); } }else{ for (auto v:A[u]){ if (v==p) continue; ll ax=avail.back()[0], ay=avail.back()[1]; res[avail.back()[2]]=v; avail.pop_back(); gen(v, u, ax, ay, avail, res); } } } void solve(){ cin >> n; pts.resize(n); A.resize(n+1); for (ll i=1; i<n; i++){ ll u, v; cin >> u >> v; A[u].push_back(v); A[v].push_back(u); } sz.resize(n+1); dfs(1, 1); for (ll i=0; i<n; i++){ cin >> pts[i][0] >> pts[i][1]; pts[i][2]=i; } sort(pts.begin(), pts.end(), [&](auto op1, auto op2){ return op1[1]>op2[1]; }); vector<ll> res(n); res[pts[0][2]]=1; vector<array<ll, 3>> avail; for (ll i=1; i<n; i++) avail.push_back(pts[i]); gen(1, 1, pts[0][0], pts[0][1], avail, res); for (ll i=0; i<n; i++) cout << res[i] << " "; cout << ln; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL auto start = chrono::high_resolution_clock::now(); #endif ll testc=1; // cin >> testc; for (ll __c=1; __c<=testc; __c++) solve(); #ifdef LOCAL auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start); cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl; #endif }
#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...