제출 #1305621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305621		loom	Drawing (CEOI22_drawing)	C++20	15 / 100	1612 ms	401568 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 cmp(pt b, pt c){
   return atan2(b.y - a.y, b.x - a.x) < atan2(c.y - a.y, c.x - a.x);
}

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);

   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: 0 / 15
• Subtask 4: 0 / 35
• Subtask 5: 0 / 25