Submission #321394

# Submission time Handle Problem Language Result Execution time Memory
321394 2020-11-12T08:42:53 Z kshitij_sodani Pastiri (COI20_pastiri) C++14
100 / 100
970 ms 106156 KB
//#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){
	if(vis[no]){
		return;
	}
	vis[no]=1;
	for(auto j:adj[no]){
		if(mi[j]==mi[no]-1){
			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 time Memory Grader output
1 Correct 298 ms 94820 KB Output is correct
2 Correct 372 ms 97636 KB Output is correct
3 Correct 346 ms 97764 KB Output is correct
4 Correct 521 ms 106156 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 12780 KB Output is correct
2 Correct 11 ms 12780 KB Output is correct
3 Correct 635 ms 72828 KB Output is correct
4 Correct 651 ms 75080 KB Output is correct
5 Correct 791 ms 73188 KB Output is correct
6 Correct 970 ms 75364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 12396 KB Output is correct
2 Correct 10 ms 12396 KB Output is correct
3 Correct 10 ms 12396 KB Output is correct
4 Correct 10 ms 12396 KB Output is correct
5 Correct 10 ms 12396 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 10 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 10 ms 12396 KB Output is correct
11 Correct 9 ms 12396 KB Output is correct
12 Correct 9 ms 12268 KB Output is correct
13 Correct 10 ms 12396 KB Output is correct
14 Correct 10 ms 12396 KB Output is correct
15 Correct 10 ms 12396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 755 ms 76132 KB Output is correct
2 Correct 762 ms 76140 KB Output is correct
3 Correct 833 ms 80588 KB Output is correct
4 Correct 777 ms 75108 KB Output is correct
5 Correct 638 ms 67912 KB Output is correct
6 Correct 865 ms 84652 KB Output is correct
7 Correct 930 ms 82636 KB Output is correct
8 Correct 935 ms 81824 KB Output is correct
9 Correct 937 ms 74876 KB Output is correct
10 Correct 815 ms 73316 KB Output is correct
11 Correct 619 ms 77812 KB Output is correct
12 Correct 600 ms 81856 KB Output is correct
13 Correct 630 ms 83952 KB Output is correct
14 Correct 543 ms 79536 KB Output is correct
15 Correct 98 ms 24100 KB Output is correct
16 Correct 823 ms 70500 KB Output is correct
17 Correct 614 ms 74460 KB Output is correct
18 Correct 736 ms 68844 KB Output is correct
19 Correct 837 ms 87520 KB Output is correct
20 Correct 872 ms 89296 KB Output is correct
21 Correct 716 ms 81292 KB Output is correct
22 Correct 742 ms 81764 KB Output is correct