Submission #384841

#	Time	Username	Problem	Language	Result	Execution time	Memory
384841		dolphingarlic	Pastiri (COI20_pastiri)	C++14	31 / 100	1075 ms	118200 KiB

pastiri

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

vector<int> graph[500001];
int sheep[500001], to_sheep[500001], depth[500001], anc[500001][19];
pair<int, int> highest[500001];
bool guarded[500001];

void dfs(int node = 1, int parent = 0, int d = 0) {
	depth[node] = d;
	for (int i = 1; i < 19; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];

	int h = node, dist = 1;
	for (int i = 18; ~i; i--) if (dist + (1 << i) == to_sheep[anc[h][i]]) {
		dist += (1 << i);
		h = anc[h][i];
	}
	highest[node] = {h, dist - 1};

	for (int i : graph[node]) if (i != parent) {
		anc[i][0] = node;
		dfs(i, node, d + 1);
	}
}

void guard(int node, int dist_rem, int parent = 0) {
	guarded[node] = true;
	if (dist_rem) for (int i : graph[node]) if (i != parent) guard(i, dist_rem - 1, node);
}

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

	queue<int> q;
	for (int i = 1; i <= k; i++) {
		cin >> sheep[i];
		q.push(sheep[i]);
		to_sheep[sheep[i]] = 1;
	}
	while (q.size()) {
		int curr = q.front();
		q.pop();
		for (int i : graph[curr]) if (!to_sheep[i]) {
			to_sheep[i] = to_sheep[curr] + 1;
			q.push(i);
		}
	}
	dfs();

	vector<int> ans;
	sort(sheep + 1, sheep + k + 1, [](int A, int B) { return depth[A] > depth[B]; });
	for (int i = 1; i <= k; i++) if (!guarded[sheep[i]]) {
		int node, dist;
		tie(node, dist) = highest[sheep[i]];
		ans.push_back(node);
		guard(node, dist);
	}
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << ' ';
	return 0;
}

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