oj.uz

답안 #877651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877651 2023-11-23T12:01:56 Z huutuan Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 122960 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], vis[N], tin[N], tout[N], tdfs;
set<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;
   tin[u]=++tdfs;
   for (int v:g[u]) if (v!=p){
      dep[v]=dep[u]+1;
      dfs(v, u);
   }
   tout[u]=tdfs;
}

void bfs(int root){
   queue<int> q;
   vector<int> vv;
   q.push(root); vis[root]=0;
   vv.push_back(root);
   while (q.size()){
      int u=q.front(); q.pop();
      if (vis[u]==dist[root]) continue;
      for (int v:g[u]) if (vis[v]==-1){
         vis[v]=vis[u]+1;
         q.push(v);
         vv.push_back(v);
      }
   }
   for (int i:vv){
      del[i]=1;
      if (tin[root]<=tin[i] && tin[i]<=tout[root]){
         for (int j:g[i]) g[j].erase(i);
         g[i].clear();
      }
      vis[i]=-1;
   }
}

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].insert(v);
      g[v].insert(u);
   }
   for (int i=1; i<=k; ++i){
      int x; cin >> x;
      a[x]=1;
   }
   bfs();
   dfs(1, 0);
   memset(vis, -1, sizeof vis);
   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

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 118308 KB Output is correct
2 Correct 197 ms 117728 KB Output is correct
3 Correct 198 ms 117776 KB Output is correct
4 Correct 261 ms 122960 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 37980 KB Output is correct
2 Correct 9 ms 38012 KB Output is correct
3 Correct 741 ms 87584 KB Output is correct
4 Correct 781 ms 87716 KB Output is correct
5 Correct 719 ms 87300 KB Output is correct
6 Execution timed out 1061 ms 93692 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 37720 KB Output is correct
2 Correct 7 ms 37724 KB Output is correct
3 Correct 7 ms 37724 KB Output is correct
4 Correct 7 ms 37468 KB Output is correct
5 Correct 7 ms 37724 KB Output is correct
6 Correct 8 ms 37724 KB Output is correct
7 Correct 8 ms 37724 KB Output is correct
8 Correct 8 ms 37720 KB Output is correct
9 Correct 8 ms 37736 KB Output is correct
10 Correct 7 ms 37724 KB Output is correct
11 Correct 8 ms 37468 KB Output is correct
12 Correct 7 ms 37468 KB Output is correct
13 Correct 11 ms 37724 KB Output is correct
14 Correct 7 ms 37724 KB Output is correct
15 Correct 9 ms 37736 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 633 ms 87568 KB Output is correct
2 Correct 629 ms 87100 KB Output is correct
3 Correct 777 ms 88880 KB Output is correct
4 Correct 611 ms 86512 KB Output is correct
5 Correct 597 ms 79336 KB Output is correct
6 Correct 795 ms 91812 KB Output is correct
7 Correct 829 ms 90684 KB Output is correct
8 Correct 859 ms 90688 KB Output is correct
9 Execution timed out 1043 ms 90728 KB Time limit exceeded
10 Halted 0 ms 0 KB -