Submission #1093116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093116		ShadowShark	Pastiri (COI20_pastiri)	C++17	100 / 100	474 ms	117172 KiB

pastiri

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

const int maxN = 5e5 + 5;
int depth[maxN], dis[maxN], par[20][maxN], done[maxN];
bool visited[maxN];
vector<int> adj[maxN];
vector<pair<int, int>> order;

void dfs(int u, int pre) {
    for (auto v: adj[u]) {
        if (v == pre) continue;
        depth[v] = depth[u] + 1;
        par[0][v] = u;
        dfs(v, u);
    }
}

void bfs() {
    queue<int> Q;
    for (auto it: order) {
        visited[it.second] = true;
        Q.push(it.second);
    }

    while (Q.size() > 0) {
        int u = Q.front(); Q.pop();
        for (auto v: adj[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            dis[v] = dis[u] + 1;
            Q.push(v);
        }
    }
}

bool cmp(pair<int, int> A, pair<int, int> B) {
    return A.first > B.first;
}

void mark_done(int u) {
    done[u] = 1;
    for (auto v: adj[u]) {
        if (done[v]) continue;
        if (dis[v] + 1 != dis[u]) continue;
        mark_done(v);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;
    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);
    }

    depth[1] = 1;
    dfs(1, 1);

    for (int j = 1; j <= 18; j++)
        for (int i = 1; i <= n; i++)
            par[j][i] = par[j - 1][par[j - 1][i]];

    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;

        order.push_back({depth[x], x});
    }

    bfs();
    sort(order.begin(), order.end(), cmp);

    //for (int i = 1; i <= n; i++)
        //cout << dis[i] << ' ';
    //cout << '\n';

    vector<int> ans;
    for (auto it: order) {
        int u = it.second;
        if (done[u]) continue;

        int x = u;
        for (int j = 18; j >= 0; j--) {
            int v = par[j][x];
            if (v != 0 && depth[u] - depth[v] == dis[v]) x = v;
        }

        //cout << u << ' ' << x << '\n';
        mark_done(x);

        //for (int i = 1; i <= n; i++)
            //cout << done[i] << ' ';
        //cout << '\n';

        ans.push_back(x);
    }

    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto v: ans)
        if (v != ans.back()) cout << v << ' ';
            else cout << v;

    return 0;
}

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