Submission #986290

#	Time	Username	Problem	Language	Result	Execution time	Memory
986290		vjudge1	Pastiri (COI20_pastiri)	C++17	31 / 100	1054 ms	65828 KiB

pastiri

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 5e5 + 5;

vector<int> g[nmax];
int dist[nmax];
int taken[nmax];

vector<int> rez;

namespace Tree {
   int p[nmax], jump[nmax], d[nmax];
   
   namespace DS {
      void fill(int node, int f, int D) {
         //if(taken[node]) return;
         taken[node] = 1;
         if(D == 0) return;
         for(auto x : g[node]) if(x != f) fill(x, node, D - 1);
      }
      void toggle() {
         return;
      }
   }
   
   void init(int node, int f) {
      d[node] = d[f] + 1;
      p[node] = jump[node] = f;
      if(d[jump[jump[f]]] + d[f] == 2 * d[jump[f]]) jump[node] = jump[jump[f]];
      
      for(auto x : g[node])
         if(x != f)
            init(x, node);
      return;
   }
   
   void fill(int node) {
      int targetfather = node;
      auto isgood = [&](int x) {
         return dist[x] == d[node] - d[x];
      };
      
      while(isgood(p[targetfather]) && targetfather != 1) {
         if(isgood(jump[targetfather])) targetfather = jump[targetfather];
         if(isgood(p[targetfather])) targetfather = p[targetfather];
      }
      
      //if(!taken[targetfather]) {
         rez.emplace_back(targetfather);
         DS::fill(targetfather, targetfather, dist[targetfather]);
      //}
      return;
   }
   
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, k;
   cin >> n >> k;
   for(int i = 1, x, y; i < n; i++) {
      cin >> x >> y;
      g[x].emplace_back(y);
      g[y].emplace_back(x);
   }
   Tree::init(1, 1);
   
   for(int i = 1; i <= n; i++) dist[i] = n + 5;
   
   vector<int> v(k);
   queue<int> que;
   for(auto &x : v) cin >> x, que.emplace(x), dist[x] = 0;
   
   while(!que.empty()) {
      int node = que.front();
      que.pop();
      
      for(auto x : g[node])
         if(dist[x] == n + 5) dist[x] = dist[node] + 1, que.emplace(x);
   }
   
   //cerr << "AA\n";
   
   sort(all(v), [&](int a, int b) { return Tree::d[a] > Tree::d[b]; });
   
   for(auto x : v) {
      if(taken[x]) continue;
      Tree::fill(x);
   }
   
   cout << sz(rez) << '\n';
   for(auto x : rez)
      cout << x << ' ';
   cout << '\n';
   
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51