Submission #1305632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305632		loom	Drawing (CEOI22_drawing)	C++20	30 / 100	1596 ms	18000 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define _ <<' '<<
#define nl '\n'

struct pt{
   int x, y, i;
};

const int N = 2e5+1;
vector<int> g[N];
int ans[N], sz[N];
pt a;

void dfs(int v, int p){
   if(p != 0) g[v].erase(find(g[v].begin(), g[v].end(), p));
   sz[v] = 1;

   for(int ch : g[v]){
      if(ch == p) continue;

      dfs(ch, v);
      sz[v] += sz[ch];
   }
}

bool miny(pt b, pt c){
   return b.y < c.y;
}

bool ps(pt p){
   return p.x >= a.x;
}

bool cmp(pt b, pt c){
   if(ps(b) == ps(c)) return (b.y - a.y) * (c.x - a.x) < (b.x - a.x) * (c.y - a.y);
   return ps(b) > ps(c);
}

void solve(int v, vector<pt>& pts){
   int i = min_element(pts.begin(), pts.end(), miny) - pts.begin();
   a = pts[i];
   ans[a.i] = v;
   pts.erase(pts.begin()+i);

   if(g[v].empty()) return;

   int ch = g[v][0];
   int k = sz[ch];

   if(g[v].size() == 1){
      solve(ch, pts);
      return;
   }

   auto s = pts.begin();
   auto e = pts.end();

   nth_element(s, s+k, e, cmp);

   vector<pt> p1(s, s+k);
   vector<pt> p2(s+k, e);

   pts = vector<pt>();

   solve(ch, p1);
   solve(g[v][1], p2);
}

void solve(){
   int n;
   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);
   }

   int r;
   for(int i = 1; i <= n; i++) if(g[i].size() == 1) r = i;

   dfs(r, 0);
   vector<pt> pts;

   for(int i = 0; i < n; i++){
      int x, y;
      cin>>x>>y;

      pts.push_back({x, y, i});
   }

   solve(r, pts);
   for(int i = 0; i < n; i++) cout<<ans[i]<<" ";
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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