Submission #1263167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263167		goulthen	Pastiri (COI20_pastiri)	C++20	100 / 100	322 ms	90324 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
 
const int MAXN = 5e5 + 10;
const int INF = 1e18 + 5;
const int MOD = 1e9 + 7;
vector<int> g[MAXN];
int a[MAXN], mk[MAXN], dist[MAXN], dep[MAXN], high[MAXN];
int cnt[MAXN], sorted[MAXN];

void dfs(int u, int p = -1, int mx = -1, int opt = 0) {
	if (dep[u] + dist[u] > mx) {
		mx = dep[u] + dist[u];
		opt = u;
	}
	high[u] = opt;
	for (int &v : g[u]) {
		if (v==p) continue;
		dep[v] = dep[u] + 1;
		dfs(v,u,mx,opt);
	}
}

void dfs2(int u) {
	mk[u] = 1;
	for (int &v : g[u]) {
		if (mk[v] || dist[u] != dist[v] +1)continue;
		dfs2(v);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int n,k;cin >> n >> k;
    rep(i,1,n) dist[i] = INF;
    rep(i,1,n-1) {
    	int u,v;cin >> u >>v;
    	g[u].pb(v);
    	g[v].pb(u);
    }

    queue<pii> bfs;
    rep(i,1,k) {
    	cin >> a[i];
    	bfs.push({0,a[i]});
    }

    while (!bfs.empty()) {
    	auto [cd, u] = bfs.front();
    	bfs.pop();
    	if (dist[u] != INF) continue;
    	dist[u] = cd;

    	for (int &v : g[u]){
    		if (dist[v] > cd + 1) bfs.push({cd+1,v});
    	}
    }

    dfs(1);

    rep(i,1,k) cnt[dep[a[i]] + 1] ++;
    rep(i,2,n) cnt[i] += cnt[i-1];
    rep(i,1,k) sorted[cnt[dep[a[i]]]++] = a[i];
    rep(i,1,k) a[i] = sorted[k-i];

    vector<int> ans;
    rep(i,1,k) {
    	if(mk[a[i]]) continue;
    	ans.pb(high[a[i]]);
    	dfs2(high[a[i]]);
    }
    cout << ans.size() << '\n';
    for (int &x : ans) cout << x << ' ';
    cout << '\n';
    

	return 0;
}

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