Submission #1106123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106123		ortsac	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	61 ms	17096 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

const int MAXN = 2e5 + 10;
vector<int> adj[MAXN];
int n, d;

pii calc(int node) {
    if (adj[node].empty()) {
        return {0, 1};
    }
    vector<pii> dec;
    for (auto u : adj[node]) {
        dec.push_back(calc(u));
    }
    sort(dec.begin(), dec.end(), greater<pii>());
    int lst = 0x3f3f3f3f, ans = 0;
    for (auto u : dec) {
        if ((lst + u.fr + 2) >= d) {
            ans += u.se;
            lst = u.fr;
        } else {
            ans += (u.se - 1);
        }
    }
    lst++;
    if (lst == d) {
        lst = 0;
        ans++;
    }
    return {lst, ans};
}

int32_t main() {
    cin >> n >> d;
    for (int i = 1  ; i < n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
    }
    cout << calc(0).se << "\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49