Submission #1278270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278270		hubertm	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	81 ms	134948 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

int n, d;
vector<int> tree[200000];
deque<int> dp[200000];

void dfs(int node, int parent)
{
    if (tree[node].size() == 1 && node != 0)
    {
        dp[node].push_back(1);
        return;
    }

    int chosen = -1;
    for (int child : tree[node])
    {
        if (child == parent) continue;

        dfs(child, node);
        
        if (chosen == -1 || dp[chosen].size() < dp[child].size()) chosen = child;
    }


    dp[node].swap(dp[chosen]);
    dp[node].push_front(1);
    if (dp[node].size() > d)
    {
        dp[node][0] += dp[node][d];
        dp[node].pop_back();
    }

    int maxD = 0;

    for (int child : tree[node])
    {
        if (child == parent || child == chosen) continue;

        maxD = max(maxD, (int) dp[child].size() + 1);

        for (int i = 0; i < min(d - 1, (int) dp[child].size()); ++i)
        {
            if (d - i - 1 < dp[node].size())
                dp[node][i + 1] = max(dp[node][i + 1], dp[child][i] + dp[node][max(0, d - i - 1)]);
            else
                dp[node][i + 1] = max(dp[node][i + 1], dp[child][i]);
        }
    }
    maxD = min(maxD, d);

    for (int i = maxD - 1; i >= 0; --i) dp[node][i] = max(dp[node][i], dp[node][i + 1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> d;

    for (int i = 1; i < n; ++i)
    {
        int p;
        cin >> p;

        tree[i].push_back(p);
        tree[p].push_back(i);
    }

    if (n == 1)
    {
        cout << "1\n";
        return 0;
    }

    dfs(0, -1);

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

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