Submission #1174035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174035		kininged	Pastiri (COI20_pastiri)	C++20	100 / 100	431 ms	61836 KiB

pastiri

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
int dist[N], deep[N], a[N], n, k, fat[N];
vector<int> e[N];
bool v[N];
void Deep(int x, int fa) {
	fat[x] = fa;
	deep[x] = deep[fa] + 1;
	for (auto y : e[x])
		if (y != fa) 
			Deep(y, x);
}
void bfs() {
	memset(dist, 0x3f, sizeof dist);
	queue<int> q;
	for (int i = 1; i <= k; ++ i) dist[a[i]] = 0, q.push(a[i]);
	while (q.size()) {
		int x = q.front(); q.pop();
		for (auto y : e[x]) {
			if (dist[y] > dist[x] + 1) {
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
}
void dfs(int x, int s) {
	v[x] = 1;
	for (auto y : e[x]) {
		if (v[y] || dist[y] != s - 1) continue;
		dfs(y, s - 1);
	}
}
int main() {
	cin >> n >> k;
	for (int i = 1, x, y; i < n; ++ i) {
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= k; ++ i) cin >> a[i];
	Deep(1, 0);
	bfs();
	sort(a + 1, a + 1 + k, [&](int x, int y) {
		return deep[x] > deep[y];
	});
	vector<int> ans;
	for (int i = 1; i <= k; ++ i) {
		if (v[a[i]]) continue;
		int now = a[i];
		while (fat[now] && dist[fat[now]] == dist[now] + 1) now = fat[now];
		dfs(now, deep[a[i]] - deep[now]);
		ans.push_back(now);
	}
	cout << ans.size() << '\n';
	for (auto x : ans)
		cout << x << ' ';
	return 0;
}

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