oj.uz

Submission #559324

# Submission time Handle Problem Language Result Execution time Memory
559324 2022-05-09T15:29:15 Z leaked Pastiri (COI20_pastiri) C++17
0 / 100
 625 ms 124048 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=5e5+1;
vec<int> gr[N];
bool used[N];
vec<int> g[N];
int d[N],h[N];
vec<int> have[N],cand[N];
int up[N];
void dfs(int v,int p,pii mx){
//    if(d[v])
//        cerr<<"WI "<<d[v]+h[v]<<' '<<v<<' '<<up[v]<<endl;
    if(mx.f<d[v]+h[v])
        umax(mx,{d[v]+h[v],v});
    up[v]=mx.s;
//     if(d[v])
//        cerr<<"WI "<<d[v]+h[v]<<' '<<v<<' '<<up[v]<<endl;
    for(auto &z : g[v]){
        if(z==p) continue;
        h[z]=h[v]+1;
        dfs(z,v,mx);
    }
}
void dfs1(int v){
    if(used[v])
        return;
    used[v]=1;
    for(auto &z : gr[v])
        dfs1(z);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fill(d,d+N,1e9);
//    ifstream cin("input.txt");
    int n,k;
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;
        g[v].pb(u);g[u].pb(v);
    }
    queue<int>q;
    vec<int> kek;
    for(int i=0;i<k;i++){
        int v;
        cin>>v;
        d[v]=0;
        q.push(v);
        kek.pb(v);
    }
//    vec<int> vc;
    while(!q.empty()){
        int v=q.front();q.pop();
        for(auto &z : g[v]){
            if(d[z]==1e9){
                d[z]=d[v]+1;
                q.push(z);
            }
        }
    }
    dfs(1,1,{-1,-1});
    for(auto &z : kek){
//        cerr<<"Z "<<z<<' '<<up[z]<<' '<<d[up[z]]<<endl;
        cand[h[z]].pb(z);
    }
    for(int i=1;i<=n;i++){
        for(auto &z : g[i]){
            if(d[i]==d[z]+1)
                gr[i].pb(z);
        }
//        have[d[i]].pb(i);
    }
    vec<int> ans;
//    vecE<
    for(int i=n-1;i>=0;i--){
        for(auto &z : cand[i]){
//            assert(d[z]==i);
            if(!used[z]){
                used[z]=1;
                ans.pb(z);
                dfs1(up[z]);
//                cout<<"SOME "<<z<<endl;
            }
        }
//        for(auto &z : have[i]){
//            if(used[z]){
//                for(auto &u : gr[z])
//                    used[u]=1;
//            }
////            for(auto &u : gr[z])
////                used[u]=1;
//        }
    }
    cout<<sz(ans)<<endl;
    for(auto &z : ans)
        cout<<z<<' ';
    return 0;
}
/*
857 20 648
3527 22 4748
4327 20 2203
3269 26 2435
4257 22 305
3325 20 4495
3689 18 4550
3030 24 2084
1980 20 3373
4251 24 1852
856 26 3184
4923 22 3812
4793 24 4786
4128 14 1
4463 18 3461
16 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 123592 KB Output is correct
2 Incorrect 244 ms 124048 KB Sheep 25 not protected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 49620 KB Sheep 857 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 49364 KB Sheep 9 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 625 ms 85764 KB Sheep 173 not protected
2 Halted 0 ms 0 KB -