Submission #321395

#TimeUsernameProblemLanguageResultExecution timeMemory
321395kshitij_sodaniPastiri (COI20_pastiri)C++14
100 / 100
957 ms106168 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second //#define endl '\n' int n,k; vector<int> adj[500001]; vector<int> ans; int lev[500001]; int par[500001][20]; int vis[500001]; int vis2[500001]; int mi[500001]; void dfs(int no,int par2=-1,int levv=0){ lev[no]=levv; par[no][0]=par2; for(auto j:adj[no]){ if(j!=par2){ dfs(j,no,levv+1); } } } //int cot=-1; //int dist[2001][2001]; /*void dfs2(int no,int par2=-1,int levv=0){ dist[cot][no]=levv; for(auto j:adj[no]){ if(j!=par2){ dfs2(j,no,levv+1); } } }*/ void dfs3(int no){ vis[no]=1; for(auto j:adj[no]){ if(mi[j]==mi[no]-1 and vis[j]==0){ dfs3(j); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>k; for(int i=0;i<n-1;i++){ int aa,bb; cin>>aa>>bb; aa--; bb--; adj[aa].pb(bb); adj[bb].pb(aa); } vector<int> ss(k); for(int i=0;i<k;i++){ cin>>ss[i]; ss[i]--; vis2[ss[i]]=1; } for(int i=0;i<n;i++){ mi[i]=n; } queue<pair<int,int>> mm; for(auto j:ss){ mi[j]=0; mm.push({0,j}); } while(mm.size()){ pair<int,int> no=mm.front(); mm.pop(); for(auto j:adj[no.b]){ if(mi[j]==n){ mi[j]=no.a+1; mm.push({mi[j],j}); } } } /*for(int i=0;i<n;i++){ cot=i; dfs2(i); }*/ dfs(0); for(int j=1;j<20;j++){ for(int i=0;i<n;i++){ if(par[i][j-1]==-1){ par[i][j]=-1; } else{ par[i][j]=par[par[i][j-1]][j-1]; } } } vector<pair<int,int>> tt; for(auto j:ss){ tt.pb({lev[j],j}); } sort(tt.begin(),tt.end()); /*for(int i=0;i<n;i++){ cout<<par[i][0]<<","; } cout<<endl; for(int i=0;i<n;i++){ cout<<par[i][1]<<","; } cout<<endl; cout<<par[19][0]<<",,"<<par[19][1]<<endl;*/ while(tt.size()){ if(vis[tt.back().b]){ tt.pop_back(); continue; } int x=tt.back().b; int cur=x; int co=0; for(int j=19;j>=0;j--){ if(par[cur][j]==-1){ continue; } if(co+(1<<j)==mi[par[cur][j]]){ cur=par[cur][j]; co+=(1<<j); } } // cout<<par[19][1]<<endl; // cout<<x<<":"<<cur<<":"<<co<<endl; /*int pp=x; int cur=par[x][0]; int co=1; while(cur!=-1){ if(co==mi[cur]){ pp=cur; cur=par[cur][0]; co++; continue; } cur=par[cur][0]; co++; } cur=pp;*/ dfs3(cur); /*for(int i=0;i<k;i++){ if(dist[cur][ss[i]]==mi[cur]){ vis[ss[i]]=1; } }*/ ans.pb(cur); tt.pop_back(); } cout<<ans.size()<<endl; for(auto j:ans){ cout<<j+1<<" "; } cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...