Submission #877272

#	Time	Username	Problem	Language	Result	Execution time	Memory
877272		socpite	Pastiri (COI20_pastiri)	C++14	100 / 100	482 ms	74784 KiB

pastiri

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

const int maxn = 5e5 + 5;

int d[maxn];

int n, k;
vector<int> g[maxn];

int mark[maxn];
int dep[maxn];
int par[maxn];
int used[maxn];
int X[maxn];

bool cmp(int a, int b)
{
    return dep[a] > dep[b];
}

void dfs(int x, int p)
{
    dep[x] = dep[p] + 1;
    par[x] = p;
    for (auto v : g[x])
    {
        if (v == p)
            continue;
        dfs(v, x);
    }
}

void bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = -1;
    }
    for (int i = 0; i < k; i++)
    {
        d[X[i]] = 0;
        q.push(X[i]);
    }
    while (!q.empty())
    {
        auto x = q.front();
        // cout << x << " " << d[x] << endl;
        q.pop();
        for (auto v : g[x])
        {
            if (d[v] != -1)
                continue;
            d[v] = d[x] + 1;
            q.push(v);
        }
    }
}

void clear(int x)
{
    mark[x] = 1;
    for (auto v : g[x])
    {
        if (mark[v] || d[v] != d[x] - 1)
            continue;
        clear(v);
    }
}

vector<int> ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < k; i++)
        cin >> X[i];
    dfs(1, 0);
    bfs();
    sort(X, X + k, cmp);
    for (int i = 0; i < k; i++)
    {
        if (mark[X[i]])
            continue;
        int crr = X[i];
        while (par[crr] && d[par[crr]] == d[crr]+1)
            crr = par[crr];
        ans.push_back(crr);
        clear(crr);
    }
    cout << ans.size() << "\n";
    for (auto v : ans)
        cout << v << " ";
}

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