oj.uz

Submission #321359

# Submission time Handle Problem Language Result Execution time Memory
321359 2020-11-12T07:48:14 Z kshitij_sodani Pastiri (COI20_pastiri) C++14
23 / 100
 1000 ms 76408 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];
int vis[500001];
int vis2[500001];
int mi[500001];
void dfs(int no,int par2=-1,int levv=0){
	lev[no]=levv;
	par[no]=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){
	if(vis2[no]){
		mi[cot]=min(mi[cot],levv);
	}
	dist[cot][no]=levv;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs2(j,no,levv+1);
		}
	}
}
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;
	}
	for(int i=0;i<n;i++){
		cot=i;
		dfs2(i);

	}
	dfs(0);
	vector<pair<int,int>> tt;
	for(auto j:ss){
		tt.pb({lev[j],j});
	}
	sort(tt.begin(),tt.end());
	while(tt.size()){
		if(vis[tt.back().b]){
			tt.pop_back();
			continue;
		}
		int x=tt.back().b;
		int cur=par[x];
		int pp=x;
		while(cur!=-1){
			if(dist[cur][x]==mi[cur]){
				pp=cur;
				cur=par[cur];
				continue;
			}
			break;
		}
		for(int i=0;i<k;i++){
			if(dist[pp][ss[i]]==mi[pp]){
				vis[ss[i]]=1;
			}
		}
		ans.pb(pp);
		tt.pop_back();
	}
	cout<<ans.size()<<endl;
	for(auto j:ans){
		cout<<j+1<<" ";
	}
	cout<<endl;











 
 
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 62564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 416 ms 76408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 27876 KB Output is correct
2 Correct 88 ms 27876 KB Output is correct
3 Correct 85 ms 27876 KB Output is correct
4 Correct 56 ms 24804 KB Output is correct
5 Correct 80 ms 28132 KB Output is correct
6 Correct 80 ms 27876 KB Output is correct
7 Correct 94 ms 27492 KB Output is correct
8 Correct 95 ms 27620 KB Output is correct
9 Correct 62 ms 27876 KB Output is correct
10 Correct 60 ms 27876 KB Output is correct
11 Correct 39 ms 22756 KB Output is correct
12 Correct 24 ms 20196 KB Output is correct
13 Correct 76 ms 26340 KB Output is correct
14 Correct 101 ms 28004 KB Output is correct
15 Correct 93 ms 27872 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 41040 KB Time limit exceeded
2 Halted 0 ms 0 KB -