oj.uz

Submission #321390

# Submission time Handle Problem Language Result Execution time Memory
321390 2020-11-12T08:39:25 Z kshitij_sodani Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 114804 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){
			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 295 ms 94716 KB Output is correct
2 Correct 349 ms 104164 KB Output is correct
3 Correct 342 ms 104292 KB Output is correct
4 Correct 500 ms 114804 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12780 KB Output is correct
2 Correct 11 ms 12780 KB Output is correct
3 Correct 662 ms 78972 KB Output is correct
4 Correct 648 ms 81340 KB Output is correct
5 Correct 804 ms 79592 KB Output is correct
6 Execution timed out 1070 ms 81692 KB Time limit exceeded

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12544 KB Output is correct
2 Correct 10 ms 12396 KB Output is correct
3 Correct 11 ms 12396 KB Output is correct
4 Correct 9 ms 12396 KB Output is correct
5 Correct 9 ms 12524 KB Output is correct
6 Correct 11 ms 12396 KB Output is correct
7 Correct 10 ms 12392 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 9 ms 12396 KB Output is correct
10 Correct 10 ms 12396 KB Output is correct
11 Correct 10 ms 12268 KB Output is correct
12 Correct 9 ms 12268 KB Output is correct
13 Correct 13 ms 12452 KB Output is correct
14 Correct 10 ms 12452 KB Output is correct
15 Correct 10 ms 12396 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 75848 KB Output is correct
2 Correct 792 ms 82432 KB Output is correct
3 Correct 869 ms 88036 KB Output is correct
4 Correct 801 ms 81284 KB Output is correct
5 Correct 662 ms 74192 KB Output is correct
6 Correct 878 ms 92944 KB Output is correct
7 Correct 964 ms 90392 KB Output is correct
8 Correct 964 ms 89344 KB Output is correct
9 Correct 990 ms 81124 KB Output is correct
10 Correct 825 ms 79552 KB Output is correct
11 Correct 652 ms 84176 KB Output is correct
12 Correct 620 ms 89536 KB Output is correct
13 Correct 654 ms 92400 KB Output is correct
14 Correct 530 ms 85668 KB Output is correct
15 Correct 99 ms 24100 KB Output is correct
16 Execution timed out 1089 ms 76224 KB Time limit exceeded
17 Halted 0 ms 0 KB -