oj.uz

Submission #321395

# Submission time Handle Problem Language Result Execution time Memory
321395 2020-11-12T08:44:18 Z kshitij_sodani Pastiri (COI20_pastiri) C++14
100 / 100
 957 ms 106168 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){
	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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 95072 KB Output is correct
2 Correct 339 ms 97920 KB Output is correct
3 Correct 334 ms 97892 KB Output is correct
4 Correct 479 ms 106168 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12780 KB Output is correct
2 Correct 11 ms 12780 KB Output is correct
3 Correct 629 ms 72316 KB Output is correct
4 Correct 618 ms 74812 KB Output is correct
5 Correct 793 ms 72872 KB Output is correct
6 Correct 957 ms 74988 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12428 KB Output is correct
2 Correct 9 ms 12396 KB Output is correct
3 Correct 10 ms 12396 KB Output is correct
4 Correct 9 ms 12396 KB Output is correct
5 Correct 10 ms 12396 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12436 KB Output is correct
9 Correct 11 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 9 ms 12396 KB Output is correct
14 Correct 9 ms 12396 KB Output is correct
15 Correct 9 ms 12396 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 75916 KB Output is correct
2 Correct 750 ms 75748 KB Output is correct
3 Correct 830 ms 80224 KB Output is correct
4 Correct 777 ms 74724 KB Output is correct
5 Correct 633 ms 67672 KB Output is correct
6 Correct 851 ms 84132 KB Output is correct
7 Correct 913 ms 82144 KB Output is correct
8 Correct 912 ms 81500 KB Output is correct
9 Correct 904 ms 74468 KB Output is correct
10 Correct 791 ms 73060 KB Output is correct
11 Correct 593 ms 77520 KB Output is correct
12 Correct 563 ms 81600 KB Output is correct
13 Correct 636 ms 83688 KB Output is correct
14 Correct 517 ms 79072 KB Output is correct
15 Correct 88 ms 23080 KB Output is correct
16 Correct 802 ms 70240 KB Output is correct
17 Correct 617 ms 67796 KB Output is correct
18 Correct 727 ms 63644 KB Output is correct
19 Correct 823 ms 80172 KB Output is correct
20 Correct 848 ms 82628 KB Output is correct
21 Correct 714 ms 74776 KB Output is correct
22 Correct 743 ms 75112 KB Output is correct