Submission #583194

#	Time	Username	Problem	Language	Result	Execution time	Memory
583194		czhang2718	Pastiri (COI20_pastiri)	C++17	100 / 100	627 ms	83508 KiB

pastiri

#include "bits/stdc++.h"
using namespace std;

typedef pair<int, int> pii;
#define f first
#define s second

const int N=5e5+1;
int n, k;
vector<int> adj[N];
bool mark[N];
int dp[N], d[N];
vector<int> ans;

void dfs(int x, int par){
	dp[x]=-1;
	if(!d[x]) mark[x]=1;
	for(int k:adj[x]){
		if(k==par) continue;
		dfs(k, x);
		if(mark[k]) mark[x]=1;
		dp[x]=max(dp[x], dp[k]-1);
	}
	if(mark[x] && dp[x]==d[x]) mark[x]=0;
	if(mark[x] && d[par]!=d[x]+1){
		ans.push_back(x);
		dp[x]=d[x];
		mark[x]=0;
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k;
	for(int i=0; i<n-1; i++){
		int u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i=1; i<=n; i++){
		d[i]=-1;
	}

	queue<int> q;
	while(k--){
		int sheep;
		cin >> sheep;
		d[sheep]=0;
		q.push(sheep);
	}

	for(; q.size(); q.pop()){
		int x=q.front();
		// cout << "d[" << x << "] " << d[x] << "\n";
		for(int k:adj[x]){
			if(d[k]==-1) d[k]=d[x]+1, q.push(k);
		}
	}

	dfs(1, 0);

	cout << ans.size() << "\n";
	for(int x:ans) cout << x << " ";
}
// does it ever get lonely thinking you could live without me?

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51