oj.uz

Submission #986289

# Submission time Handle Problem Language Result Execution time Memory
986289 2024-05-20T09:05:13 Z vjudge1 Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 65824 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;
         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';
   
}

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 61008 KB Output is correct
2 Correct 146 ms 61108 KB Output is correct
3 Correct 150 ms 61104 KB Output is correct
4 Correct 219 ms 65824 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21852 KB Output is correct
2 Correct 6 ms 21816 KB Output is correct
3 Correct 292 ms 44592 KB Output is correct
4 Correct 331 ms 46932 KB Output is correct
5 Correct 473 ms 44508 KB Output is correct
6 Execution timed out 1039 ms 46528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21684 KB Output is correct
2 Correct 5 ms 21852 KB Output is correct
3 Correct 5 ms 21852 KB Output is correct
4 Correct 5 ms 21848 KB Output is correct
5 Correct 5 ms 22104 KB Output is correct
6 Correct 5 ms 21852 KB Output is correct
7 Correct 5 ms 21852 KB Output is correct
8 Correct 5 ms 21848 KB Output is correct
9 Correct 5 ms 21812 KB Output is correct
10 Correct 5 ms 21848 KB Output is correct
11 Correct 6 ms 21812 KB Output is correct
12 Correct 4 ms 21852 KB Output is correct
13 Correct 5 ms 21852 KB Output is correct
14 Correct 5 ms 21852 KB Output is correct
15 Correct 5 ms 21848 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 38428 KB Output is correct
2 Correct 377 ms 44884 KB Output is correct
3 Correct 392 ms 48604 KB Output is correct
4 Correct 391 ms 44368 KB Output is correct
5 Correct 292 ms 44232 KB Output is correct
6 Correct 393 ms 52380 KB Output is correct
7 Correct 468 ms 50760 KB Output is correct
8 Correct 472 ms 50256 KB Output is correct
9 Execution timed out 1059 ms 44316 KB Time limit exceeded
10 Halted 0 ms 0 KB -