Submission #559326

#	Time	Username	Problem	Language	Result	Execution time	Memory
559326		leaked	Pastiri (COI20_pastiri)	C++17	100 / 100	744 ms	128720 KiB

pastiri

#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])
        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(up[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: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51