Submission #581679

#	Time	Username	Problem	Language	Result	Execution time	Memory
581679		PurpleCrayon	Pastiri (COI20_pastiri)	C++17	100 / 100	673 ms	71712 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e5+10, MOD = 1e9+7;

int n, k, a[N], depth[N], d[N], par[N];
vector<int> adj[N];
bool mark[N];

void dfs(int c, int p) {
    par[c] = p;
    for (auto nxt : adj[c]) if (nxt != p) {
        depth[nxt] = depth[c] + 1;
        dfs(nxt, c);
    }
}
void mark_node(int c) {
    if (mark[c]) return;

    mark[c] = 1;
    for (auto nxt : adj[c]) if (d[nxt] == d[c] - 1)
        mark_node(nxt);
}
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    dfs(0, -1);
    std::fill(d, d + n, MOD);
    vector<int> q; q.reserve(n);
    for (int i = 0; i < k; i++) {
        int c; cin >> c, --c;
        a[i] = c;
        d[c] = 0; q.push_back(c);
    }

    for (int rep = 0; rep < sz(q); rep++) {
        int c = q[rep];
        for (auto nxt : adj[c]) if (d[nxt] > d[c] + 1) {
            d[nxt] = d[c] + 1;
            q.push_back(nxt);
        }
    }

    sort(a, a + n, [&](int x, int y) { return depth[x] > depth[y]; });

    int ans = 0;
    vector<int> pr; pr.reserve(n);
    for (int i = 0; i < k; i++) if (!mark[a[i]]) {
        int use = a[i];
        while (par[use] != -1 && d[par[use]] == depth[a[i]] - depth[par[use]]) {
            use = par[use];
        }
        pr.push_back(use);
        ans++;
        mark_node(use);
    }
    cout << ans << '\n';
    for (int x : pr) cout << x+1 << ' ';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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