Submission #581623

#	Time	Username	Problem	Language	Result	Execution time	Memory
581623		penguinhacker	Pastiri (COI20_pastiri)	C++17	100 / 100	539 ms	85032 KiB

pastiri

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

#define ll long long
#define ar array

const int mxN=5e5;
int n, k, d[mxN], dp[mxN], mark[mxN];
vector<int> adj[mxN], ans;

void dfs(int u=0, int p=-1) {
	mark[u]=-1;
	dp[u]=d[u]?-1:0;
	for (int v : adj[u])
		if (v!=p) {
			dfs(v, u);
			if (dp[v]!=-1)
				dp[u]=max(dp[u], dp[v]+1);
			mark[u]=max(mark[u], mark[v]-1);
		}
	if (dp[u]==-1||mark[u]>=dp[u]) { // this is covered
		dp[u]=-1;
		return;
	}
	//cout << u << " " << dp[u] << " " << mark[u] << endl;
	if (!u||(u&&dp[u]+1>d[p])) { // must place a pastir here
		dp[u]=-1;
		mark[u]=d[u];
		ans.push_back(u);	
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(d, -1, sizeof(d));
	queue<int> q;
	for (int i=0; i<k; ++i) {
		int x;
		cin >> x, --x;
		d[x]=0;
		q.push(x);
	}
	for (; q.size(); q.pop()) {
		int u=q.front();
		for (int v : adj[u])
			if (d[v]==-1) {
				d[v]=d[u]+1;
				q.push(v);
			}
	}
	//for (int i=0; i<n; ++i)
	//	cout << d[i] << endl;
	dfs();
	cout << ans.size() << "\n";
	for (int i : ans)
		cout << i+1 << " ";
	return 0;
}

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