Submission #1262998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262998		goulthen	Pastiri (COI20_pastiri)	C++20	0 / 100	284 ms	84656 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], dd[MAXN], cvr[MAXN], mk2[MAXN];

void dfs(int u, int p = -1) {
	if (a[u]) dd[u] = 0;
	int d = INF;
	for (int &v : g[u]) {
		if (v==p) continue;
		dfs(v,u);
		dd[u] = min(dd[u], dd[v]+1);
		cvr[u] = max(cvr[u], cvr[v] - 1);
	}
	for (int &v : g[u]) {
		if (v==p) continue;
		if (dist[u] - 1 < dd[v] && dd[v] < INF && dd[v] > cvr[v]) {
			mk[v] = 1;
			cvr[u] = max(cvr[u],dd[v] - 1);
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int n,k;cin >> n >> k;
    rep(i,1,n) dist[i] = dd[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) {
    	int p;cin >> p;
    	a[p] = 1;
    	bfs.push({0,p});
    }

    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);
    vector<int> cnd;

    rep(i,2,n) if (mk[i]) bfs.push({dist[i]+1,i});

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

    	for (int &v : g[u]){
    		if (!mk2[v]) bfs.push({cd-1,v});
    	}
    }
    //rep(i,1,n) cout << i << ' ' << dist[i] << ' ' << mk2[i] << '\n';
    rep(i,1,n) if (a[i] && !mk2[i] && cnd.empty()) cnd.pb(1);
    rep(i,1,n) if (mk[i]) cnd.pb(i);
    cout << cnd.size() << '\n';
    for (auto &x : cnd) cout << x << ' ';
    cout << '\n';

	return 0;
}

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