oj.uz

Submission #877657

# Submission time Handle Problem Language Result Execution time Memory
877657 2023-11-23T12:12:46 Z huutuan Pastiri (COI20_pastiri) C++14
100 / 100
 485 ms 73676 KB 
#include<bits/stdc++.h>
#define taskname "sheep"

using namespace std;

const int N=5e5+1;
int n, k, a[N], dep[N], par[N], dist[N], del[N];
vector<int> g[N];

void bfs(){
   memset(dist, -1, sizeof dist);
   queue<int> q;
   for (int i=1; i<=n; ++i) if (a[i]) q.push(i), dist[i]=0;
   while (q.size()){
      int u=q.front(); q.pop();
      for (int v:g[u]) if (dist[v]==-1){
         dist[v]=dist[u]+1;
         q.push(v);
      }
   }
}

void dfs(int u, int p){
   par[u]=p;
   for (int v:g[u]) if (v!=p){
      dep[v]=dep[u]+1;
      dfs(v, u);
   }
}
 
void bfs(int root){
   queue<int> q;
   vector<int> vv;
   q.push(root);
   while (q.size()){
      int u=q.front(); q.pop();
      for (int v:g[u]) if (!del[v] && dist[v]==dist[u]-1){
         del[v]=1;
         q.push(v);
      }
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   // freopen(taskname".inp", "r", stdin);
   // freopen(taskname".out", "w", stdout);
   cin >> n >> k;
   for (int i=1; i<n; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i=1; i<=k; ++i){
      int x; cin >> x;
      a[x]=1;
   }
   bfs();
   dfs(1, 0);
   vector<int> vv;
   for (int i=1; i<=n; ++i) if (a[i]) vv.push_back(i);
   sort(vv.begin(), vv.end(), [&](int x, int y){
      return dep[x]<dep[y];
   });
   vector<int> ans;
   while (vv.size()){
      int u=vv.back(); vv.pop_back();
      int v=u;
      while (dist[par[v]]==dep[u]-dep[par[v]]) v=par[v];
      ans.push_back(v);
      bfs(v);
      while (vv.size() && del[vv.back()]) vv.pop_back();
   }
   cout << ans.size() << '\n';
   for (int i:ans) cout << i << ' ';
   return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 68036 KB Output is correct
2 Correct 152 ms 68572 KB Output is correct
3 Correct 160 ms 68508 KB Output is correct
4 Correct 188 ms 73676 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 281 ms 37372 KB Output is correct
4 Correct 258 ms 39304 KB Output is correct
5 Correct 354 ms 36908 KB Output is correct
6 Correct 441 ms 39824 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 6 ms 19052 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Correct 5 ms 19036 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 38540 KB Output is correct
2 Correct 354 ms 38484 KB Output is correct
3 Correct 432 ms 40344 KB Output is correct
4 Correct 365 ms 37632 KB Output is correct
5 Correct 277 ms 37060 KB Output is correct
6 Correct 399 ms 44252 KB Output is correct
7 Correct 449 ms 42812 KB Output is correct
8 Correct 441 ms 42912 KB Output is correct
9 Correct 485 ms 37748 KB Output is correct
10 Correct 421 ms 43356 KB Output is correct
11 Correct 288 ms 46252 KB Output is correct
12 Correct 253 ms 49528 KB Output is correct
13 Correct 307 ms 52324 KB Output is correct
14 Correct 197 ms 47416 KB Output is correct
15 Correct 32 ms 23132 KB Output is correct
16 Correct 398 ms 42572 KB Output is correct
17 Correct 294 ms 43716 KB Output is correct
18 Correct 356 ms 39504 KB Output is correct
19 Correct 406 ms 50060 KB Output is correct
20 Correct 393 ms 53688 KB Output is correct
21 Correct 332 ms 44440 KB Output is correct
22 Correct 330 ms 44920 KB Output is correct