3296 2023. 02. 24 14:11:11 zsombor Szállítás cpp17 Elfogadva 40/40 13ms 6204 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, k, ans = 0;
vector <int> p(2e4 + 1, 0);
vector <int> d(2e4 + 1, 0);
vector <int> mxd(2e4 + 1, 0);
vector <vector <int>> g(2e4 + 1);
vector <pair <int, int>> l;

void atrendez(int x) {
    mxd[x] = d[x];
    int mxi = 0;
    for (int i : g[x]) {
        d[i] = d[x] + 1;
        atrendez(i);
        mxd[x] = max(mxd[x], mxd[i]);
        if (mxd[i] > mxd[mxi]) { p[mxi] = 1; mxi = i; }
        else p[i] = 1;
    }
}

void level(int x) {
    if (!g[x].size()) l.push_back({ -d[x],x });
    for (int i : g[x]) {
        d[i] = d[x] + 1;
        level(i);
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        g[p[i]].push_back(i);
    }
    atrendez(1);
    for (int i = 1; i <= n; i++) g[i].resize(0);
    for (int i = 1; i <= n; i++) g[p[i]].push_back(i);
    level(1);
    for (int i = 1; i <= n; i++) if (g[i].size() && l.size() < k) l.push_back({ 0,i });
    sort(l.begin(), l.end());
    for (int i = 0; i < k; i++) ans -= l[i].first;
    cout << ans << endl;
    for (int i = 0; i < k; i++) cout << l[i].second << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 2904 KiB
2 Elfogadva 0/0 6ms 3792 KiB
3 Elfogadva 2/2 3ms 3508 KiB
4 Elfogadva 2/2 3ms 3796 KiB
5 Elfogadva 2/2 4ms 4012 KiB
6 Elfogadva 2/2 3ms 3872 KiB
7 Elfogadva 2/2 3ms 3792 KiB
8 Elfogadva 2/2 4ms 4048 KiB
9 Elfogadva 2/2 4ms 4132 KiB
10 Elfogadva 2/2 3ms 4136 KiB
11 Elfogadva 2/2 4ms 4260 KiB
12 Elfogadva 2/2 4ms 4520 KiB
13 Elfogadva 2/2 6ms 5048 KiB
14 Elfogadva 2/2 6ms 5148 KiB
15 Elfogadva 2/2 6ms 5164 KiB
16 Elfogadva 2/2 7ms 5228 KiB
17 Elfogadva 3/3 7ms 5680 KiB
18 Elfogadva 3/3 8ms 5760 KiB
19 Elfogadva 3/3 13ms 6204 KiB
20 Elfogadva 3/3 13ms 6184 KiB