Submission #1286033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286033		domi	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	40 ms	21048 KiB

catinatree

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 2e5;

using namespace std;

vector<int>T[NMAX + 5];
int dp[NMAX + 5], closestDistance[NMAX + 5], n, d;

void dfs(int nod) {
    if (sz(T[nod]) == 0) {
        dp[nod] = 1;
        closestDistance[nod] = 1;
        return;
    }

    vector<pii>distances;
    for (auto &son : T[nod]) {
        dfs(son);
        distances.push_back({closestDistance[son], son});
        dp[nod] += dp[son];
    }

    sort(all(distances));
    int firstChild = 0, c = distances[0].se;
    for (int i = 0; i + 1 < sz(distances); ++i) {
        if (distances[i].fi + distances[i + 1].fi < d) {
            --dp[nod];
            firstChild = i + 1;
            c = distances[i + 1].se;
        }
    }

    if (distances[firstChild].fi >= d) {
        ++dp[nod];
        closestDistance[nod] = 1;
    }
    else
        closestDistance[nod] = closestDistance[c] + 1;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> d;

    for (int i = 1, u; i < n; ++i) {
        cin >> u;
        T[u].push_back(i);
    }

    dfs(0);
    cout << dp[0] << '\n';
    return 0;
}

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