Submission #481062

#	Time	Username	Problem	Language	Result	Execution time	Memory
481062		Rainbowbunny	Pastiri (COI20_pastiri)	C++17	49 / 100	1099 ms	140724 KiB

pastiri

#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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51