Submission #467345

#	Time	Username	Problem	Language	Result	Execution time	Memory
467345		phathnv	Pastiri (COI20_pastiri)	C++11	41 / 100	1096 ms	93396 KiB

pastiri

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

const int N = 500007;

int n, k, sheep[N], h[N], d[N], trace[N], numNode;
pair<int, int> best[2 * N];
vector<int> adj[N], child[2 * N];
bool vst[N];

int main() {
    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);
    }
    for (int i = 1; i <= k; i++)
        cin >> sheep[i];
    queue<int> qu;
    h[1] = 1;
    qu.push(1);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : adj[u])
            if (!h[v]) {
                h[v] = h[u] + 1;
                qu.push(v);
            }
    }
    for (int i = 1; i <= k; i++) {
        int x = sheep[i];
        ++numNode;
        best[numNode] = {h[x], numNode};
        trace[x] = numNode;
        d[x] = 1;
        qu.push(x);
    }
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : adj[u]) {
            if (!d[v]) {
                trace[v] = best[trace[u]].second;
                d[v] = d[u] + 1;
                qu.push(v);
            } else if (d[v] == d[u] + 1) {
                int newNode = ++numNode;
                child[newNode].push_back(trace[u]);
                child[newNode].push_back(trace[v]);
                best[newNode] = {min(best[trace[u]].first, best[trace[v]].first), newNode};
                vst[trace[u]] = vst[trace[v]] = true;
                trace[v] = newNode;
            }
        }
    }
    for (int u = 1; u <= numNode; u++)
        if (vst[u]) {
            vst[u] = false;
            best[u] = {1e9, 1e9};
        }
    for (int u = numNode; u >= 1; u--) {
        for (int v : child[u])
            best[v] = min(best[v], best[u]);
    }
    vector<int> ord(k);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](const int &a, const int &b){
            return h[sheep[a]] > h[sheep[b]];
         });
    map<int, int> nodeToVex;
    for (int i = 1; i <= n; i++)
        nodeToVex[trace[i]] = i;
    vector<int> answer;
    for (int x : ord) {
        if (vst[x])
            continue;
        queue<int> qu;
        qu.push(best[x].second);
        answer.push_back(nodeToVex[best[x].second]);
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            if (vst[u])
                continue;
            vst[u] = true;
            for (int v : child[u])
                qu.push(v);
        }
    }
    cout << answer.size() << '\n';
    for (int x : answer)
        cout << x << ' ';
    cout << '\n';
}

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