oj.uz

Submission #559323

# Submission time Handle Problem Language Result Execution time Memory
559323 2022-05-09T15:28:37 Z leaked Pastiri (COI20_pastiri) C++17
0 / 100
 606 ms 123980 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(up[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 200 ms 123572 KB Output is correct
2 Incorrect 258 ms 123980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 51.0

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