Submission #1305398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305398		loom	Drawing (CEOI22_drawing)	C++20	30 / 100	1597 ms	20492 KiB

Main

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

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

void dfs(int v, int p){
   sz[v] = 1;
   
   for(int ch : g[v]){
      if(ch == p) continue;

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

T top(set<T>& st){
   T p = {-inf, -inf, -inf};
   
   for(auto [x, y, i] : st){
      auto [px, py, pi] = p;

      if(y > py or y == py and x < px) p = {x, y, i};
   }

   return p;
}

void solve(int v, int p, set<T>& st){
   auto [rx, ry, ri] = top(st);
   ans[ri] = v;
   st.erase({rx, ry, ri});

   if(p != 0) g[v].erase(find(g[v].begin(), g[v].end(), p));
   sort(g[v].begin(), g[v].end(), [&](int x, int y){
      return sz[x] < sz[y];
   });

   for(int i = 0; i < g[v].size(); i++){
      int ch = g[v][i];

      if(i+1 == g[v].size()){
         solve(ch, v, st);
         continue;
      }

      set<T> nst;

      for(int j = 0; j < sz[ch]; j++){
         auto [x, y, ix] = *st.begin();
         st.erase(st.begin());
         nst.insert({x, y, ix});
      }

      solve(ch, v, nst);
   }
}

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

   set<T> st;

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

      st.insert({x, y, i});
   }

   dfs(1, 0);
   solve(1, 0, st);

   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