Submission #1004094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004094		vjudge1	Pastiri (COI20_pastiri)	C++17	41 / 100	1053 ms	149124 KiB

pastiri

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

const int N = 5e5 + 10;
int n, k, a[N], par[N], h[N];
vector<int> g[N];
set<int> poss[N];

bool mark[N];
map<int, bool> exist;

vector<int> bfs(vector<int> sources){
    vector<int> dist(n + 1, N + 10);
    
    queue<int> q;
    for (int v : sources){
        dist[v] = 0;
        poss[v] = {v};
        q.push(v);
    }

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                q.push(u);
                dist[u] = dist[v] + 1;
                poss[u] = poss[v];
            }
            else if (dist[u] == dist[v] + 1){
                for (int x : poss[v])
                    poss[u].insert(x);
            }
        }
    }

    return dist;
}

void bfs2(int v, int d){
    vector<int> dist(n + 1, N + 10);
    dist[v] = 0;

    queue<int> q;
    q.push(v);

    while (!q.empty()){
        int v = q.front();
        q.pop();

        if (dist[v] == d and exist[v])
            mark[v] = 1;

        if (dist[v] >= d) continue;
    
        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

void dfs(int v, int p = -1){
    par[v] = p;
    for (int u : g[v]){
        if (u == p) continue;

        h[u] = h[v] + 1;
        dfs(u, v);
    }
}

int main(){
    cin >> n >> k;

    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> vec;
    for (int i = 0; i < k; i ++)
        cin >> a[i], vec.push_back(a[i]), exist[a[i]] = 1;

    dfs(1);

    set<pair<int, int>> st;
    for (int i = 0; i < k; i ++)
        st.insert({h[a[i]], a[i]});

    vector<int> dist = bfs(vec);
    vector<int> res;
    while (!st.empty()){
        int v = (*st.rbegin()).second;
        st.erase({h[v], v});

        // cout << "At vertex = " << v << endl;

        if (mark[v]) continue;

        int cur = v;
        while (par[cur] != -1 and dist[par[cur]] == (h[v] - h[par[cur]]))
            cur = par[cur];

        bfs2(cur, dist[cur]);

        res.push_back(cur);

        // cout << "Selected " << cur << endl;
    }

    cout << res.size() << endl;
    for (int x : res)
        cout << x << " ";
    cout << endl;
}

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