oj.uz

Submission #384841

# Submission time Handle Problem Language Result Execution time Memory
384841 2021-04-02T12:31:30 Z dolphingarlic Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 118200 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 110828 KB Output is correct
2 Correct 418 ms 111276 KB Output is correct
3 Correct 428 ms 111212 KB Output is correct
4 Correct 551 ms 118200 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12780 KB Output is correct
2 Correct 13 ms 12780 KB Output is correct
3 Correct 758 ms 80392 KB Output is correct
4 Correct 723 ms 82924 KB Output is correct
5 Execution timed out 1075 ms 79872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 12 ms 12396 KB Output is correct
5 Correct 11 ms 12396 KB Output is correct
6 Correct 11 ms 12396 KB Output is correct
7 Correct 10 ms 12396 KB Output is correct
8 Correct 12 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 10 ms 12524 KB Output is correct
11 Correct 11 ms 12268 KB Output is correct
12 Correct 10 ms 12268 KB Output is correct
13 Correct 13 ms 12396 KB Output is correct
14 Correct 11 ms 12396 KB Output is correct
15 Correct 11 ms 12396 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 81004 KB Output is correct
2 Correct 904 ms 80792 KB Output is correct
3 Correct 835 ms 84296 KB Output is correct
4 Correct 896 ms 79820 KB Output is correct
5 Correct 665 ms 70884 KB Output is correct
6 Correct 961 ms 88884 KB Output is correct
7 Execution timed out 1010 ms 86940 KB Time limit exceeded
8 Halted 0 ms 0 KB -