oj.uz

Submission #986291

# Submission time Handle Problem Language Result Execution time Memory
986291 2024-05-20T09:10:50 Z vjudge1 Pastiri (COI20_pastiri) C++17
8 / 100
 441 ms 65868 KB 
#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;
         //cerr << node << ' ' << f << ' ' << D << '\n';
         
         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];
      }
      
      rez.emplace_back(targetfather);
      for(int i = 0; i < dist[targetfather]; i++) {
         DS::fill(node, p[node], i);
         node = p[node];
      }
      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';
   
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 61116 KB Output is correct
2 Correct 145 ms 61016 KB Output is correct
3 Correct 156 ms 61268 KB Output is correct
4 Correct 207 ms 65868 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 21852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 21852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 38472 KB Output isn't correct
2 Halted 0 ms 0 KB -