Submission #586836

#	Time	Username	Problem	Language	Result	Execution time	Memory
586836		MetalPower	Pastiri (COI20_pastiri)	C++14	100 / 100	737 ms	109708 KiB

pastiri

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

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 5e5 + 10;
const int LG = 20;
const int INF = 1e9 + 7;

int N, K, dep[MX], sp[MX][LG];
vector<int> adj[MX];
vector<pii> s;

void dfs(int u, int v){

	dep[u] = dep[v] + 1;
	sp[u][0] = v;

	for(int nxt : adj[u]){
		if(nxt == v) continue;
		dfs(nxt, u);
	}
}

int dt[MX];
bool used[MX];

void bfs(){

	for(int i = 0; i < MX; i++) dt[i] = INF;

	queue<pii> q;
	for(pii x : s){
		dt[x.se] = 0;
		q.push({0, x.se});
	}

	while(!q.empty()){

		int cd = q.front().fi, cr = q.front().se;
		q.pop();

		for(int nxt : adj[cr]){
			if(dt[nxt] > cd + 1){
				dt[nxt] = cd + 1;
				q.push({dt[nxt], nxt});
			}
		}
	}
}

void mark(int u, int ndist){

	if(dt[u] == ndist) used[u] = 1;
	else return;

	for(int nxt : adj[u]){
		if(used[nxt]) continue;
		mark(nxt, ndist - 1);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.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);
	}

	dfs(1, 0);

	for(int i = 1; i <= K; i++){
		int u; cin >> u;
		s.push_back({dep[u], u});
	}

	for(int k = 1; k < LG; k++){
		for(int i = 1; i <= N; i++){
			sp[i][k] = sp[sp[i][k - 1]][k - 1];
		}
	}

	sort(s.begin(), s.end(), greater<pii>());

	bfs();

	vector<int> ans;

	for(int i = 0; i < K; i++){

		int u = s[i].se, dist = 0;

		if(used[u]) continue;

		for(int k = LG - 1; k >= 0; k--){
			if(sp[u][k] != 0 && dt[sp[u][k]] == (dist + (1 << k))){
				u = sp[u][k], dist += 1 << k;
			}
		}

		ans.push_back(u);
		mark(u, dt[u]);
	}

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

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