oj.uz

Submission #481062

# Submission time Handle Problem Language Result Execution time Memory
481062 2021-10-19T11:29:55 Z Rainbowbunny Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 140724 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fi first
#define se second
const int N = 5e5 + 5;

int n, k;
vector<int> adj[N];
vector<int> G[N];
int sheep[N];
int h[N], par[N][20];
int dist[N], vis[N];
multiset<pair<int, int> > ms;
vector<int> ans;

void dfs(int u, int p) {
	for (int v : adj[u]) {
		if (v != p) {
			h[v] = h[u] + 1;
			par[v][0] = u;
			dfs(v, u);	
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

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

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 18; j++) {
			par[i][j] = -1;
		}
	}
	h[1] = 1; dfs(1, 1);
	for (int j = 1; j <= 18; j++) {
		for (int i = 1; i <= n; i++) {
			if (par[i][j - 1] != -1) {
				par[i][j] = par[par[i][j - 1]][j - 1];
			}
		}
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (sheep[i] == 1) {
			q.push(i);
		} else {
			dist[i] = 1e9;
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int v : adj[u]) {
			if (dist[v] == 1e9) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (sheep[i] == 1) ms.insert({-h[i], i});
		for (int v : adj[i]) {
			if (dist[i] == dist[v] + 1) G[i].push_back(v);
		}
	}

	while (!ms.empty()) {
		int pre = ms.begin() -> se;
		int cur = pre;
		for (int i = 18; i >= 0; i--) {
			if (par[cur][i] != -1 && dist[par[cur][i]] == h[pre] - h[par[cur][i]]) {
				cur = par[cur][i];
			}
		}

		vector<int> take;
		q.push(cur); vis[cur] = 1;
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			if (dist[u] == 0) take.push_back(u);
			for (int v : G[u]) {
				if (vis[v] == 0) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}

		for (int i : take) ms.erase(ms.find({-h[i], i}));
		ans.push_back(cur);
	}

	cout << (int)ans.size() << "\n";
	for (int i : ans) cout << i << " ";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 129824 KB Output is correct
2 Correct 355 ms 132684 KB Output is correct
3 Correct 360 ms 132676 KB Output is correct
4 Correct 497 ms 140724 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24524 KB Output is correct
2 Correct 18 ms 24520 KB Output is correct
3 Correct 623 ms 98616 KB Output is correct
4 Correct 661 ms 100536 KB Output is correct
5 Correct 896 ms 100200 KB Output is correct
6 Correct 971 ms 103000 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24164 KB Output is correct
2 Correct 19 ms 24128 KB Output is correct
3 Correct 18 ms 24148 KB Output is correct
4 Correct 16 ms 24016 KB Output is correct
5 Correct 15 ms 24244 KB Output is correct
6 Correct 17 ms 24124 KB Output is correct
7 Correct 17 ms 24096 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 16 ms 24140 KB Output is correct
11 Correct 15 ms 24060 KB Output is correct
12 Correct 16 ms 24012 KB Output is correct
13 Correct 19 ms 24092 KB Output is correct
14 Correct 17 ms 24140 KB Output is correct
15 Correct 15 ms 24120 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 103100 KB Output is correct
2 Correct 806 ms 102912 KB Output is correct
3 Correct 990 ms 106792 KB Output is correct
4 Correct 812 ms 102060 KB Output is correct
5 Correct 709 ms 91572 KB Output is correct
6 Execution timed out 1099 ms 112832 KB Time limit exceeded
7 Halted 0 ms 0 KB -