Submission #363507

#	Time	Username	Problem	Language	Result	Execution time	Memory
363507		mihai145	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	358 ms	171752 KiB

catinatree

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int NMAX = 2e5;

int N, D;
vector<int> g[NMAX + 5];

int depth[NMAX + 5];
deque<int> dp[NMAX + 5];

vector<int> sumD;
vector<int> maxForD;

void dfs(int node) {

    if (g[node].empty()) {
        dp[node].push_back(1);
        return;
    }

    depth[node] = 1;
    for (auto it : g[node]) {
        dfs(it);
        depth[node] = max(depth[node], 1 + depth[it]);
    }

    ///GET DEEPEST CHILD
    int deepestChild = -1;
    for (auto it : g[node]) {
        if (deepestChild == -1) {
            deepestChild = it;
        } else if (depth[it] > depth[deepestChild]) {
            deepestChild = it;
        }
    }

    ///GET SECOND DEPTH
    int secondDepth = 0;
    for (auto it : g[node]) {
        if (it != deepestChild) {
            secondDepth = max(secondDepth, depth[it]);
        }
    }

    ///CALCULATE sumD and maxForD (up to secondDepth)
    maxForD.resize(secondDepth + 2);
    sumD.resize(secondDepth + 2);
    for (int i = 0; i <= secondDepth + 1; i++)
        sumD[i] = maxForD[i] = 0;

    for (auto it : g[node]) {
        int lim = min(D / 2, min(secondDepth + 1, depth[it] + 1));
        for (int d = 1; d <= lim; d++) {

            int f = 0;
            if (depth[it] >= D - d - 1) {
                f = dp[it][D - d - 1];
            }

            maxForD[d] = max(maxForD[d], dp[it][d - 1] - f);
            sumD[d] += f;
        }
    }

    ///CALCULATE DP[node][0]
    int sum = 1;
    for (auto it : g[node]) {
        if (depth[it] >= D - 1) {
            sum += dp[it][D - 1];
        }
    }

    ///CALCULATE DP[node][d] for 2 * d >= D
    swap(dp[node], dp[deepestChild]);
    dp[node].push_front(sum);

    for (auto it : g[node]) {
        if (it != deepestChild) {
            for (int d = 1; d <= min(D - 1, depth[it] + 1); d++)
                dp[node][d] += dp[it][d - 1];
        }
    }

    ///CALCULATE DP[node][d] for 2 * d < D
    for (int d = 1; d <= min(secondDepth + 1, D / 2); d++)
        dp[node][d] = sumD[d] + maxForD[d];

    ///PROPAGATING DP[node][d] = max(DP[node][d], DP[node][d + 1])
    for (int d = min(secondDepth, D - 2); d >= 0; d--)
        dp[node][d] = max(dp[node][d], dp[node][d + 1]);
}

int main() {
    cin >> N >> D;

    for (int i = 1; i < N; i++) {
        int x;
        cin >> x;
        g[x].push_back(i);
    }

    dfs(0);

    cout << dp[0][0] << '\n';

    return 0;
}

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