oj.uz

Submission #321388

# Submission time Handle Problem Language Result Execution time Memory
321388 2020-11-12T08:38:16 Z kshitij_sodani Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 106244 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 289 ms 94692 KB Output is correct
2 Correct 347 ms 97508 KB Output is correct
3 Correct 340 ms 97784 KB Output is correct
4 Correct 526 ms 106244 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12780 KB Output is correct
2 Correct 11 ms 12780 KB Output is correct
3 Correct 712 ms 72532 KB Output is correct
4 Correct 742 ms 74684 KB Output is correct
5 Correct 823 ms 72932 KB Output is correct
6 Execution timed out 1056 ms 75108 KB Time limit exceeded

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 11 ms 12396 KB Output is correct
5 Correct 9 ms 12396 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 11 ms 12396 KB Output is correct
8 Correct 9 ms 12396 KB Output is correct
9 Correct 9 ms 12396 KB Output is correct
10 Correct 9 ms 12396 KB Output is correct
11 Correct 11 ms 12268 KB Output is correct
12 Correct 9 ms 12288 KB Output is correct
13 Correct 12 ms 12396 KB Output is correct
14 Correct 10 ms 12396 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 816 ms 76112 KB Output is correct
2 Correct 858 ms 75848 KB Output is correct
3 Correct 863 ms 80048 KB Output is correct
4 Correct 797 ms 74724 KB Output is correct
5 Correct 641 ms 67540 KB Output is correct
6 Correct 878 ms 84208 KB Output is correct
7 Correct 965 ms 82144 KB Output is correct
8 Correct 975 ms 81424 KB Output is correct
9 Correct 983 ms 74500 KB Output is correct
10 Correct 861 ms 72932 KB Output is correct
11 Correct 725 ms 77408 KB Output is correct
12 Correct 625 ms 81600 KB Output is correct
13 Correct 692 ms 83688 KB Output is correct
14 Correct 557 ms 79016 KB Output is correct
15 Correct 111 ms 23076 KB Output is correct
16 Execution timed out 1086 ms 70104 KB Time limit exceeded
17 Halted 0 ms 0 KB -