Submission #1207843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207843		NHristov	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	49 ms	27324 KiB

catinatree

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 2e5 + 5;

int n, d;

vector < int > g[N];

struct Deque
{
    vector < int > v;

    int size()
    {
        return v.size();
    }

    void push_front(int push)
    {
        v.push_back(push);
    }

    int &operator [](int idx)
    {
        return v.rbegin()[idx];
    }

    void clear()
    {
        vector < int > ().swap(v);
    }
};

Deque dp[N];

void dfs(int u)
{
    int big = 0, sz = 0;

    for (int v : g[u])
    {
        dfs(v);

        if (sz < dp[v].size())
        {
            big = v;
            sz = dp[v].size();
        }
    }

    if (g[u].empty())
    {
        dp[u].push_front(1);

        return;
    }

    dp[u].v.swap(dp[big].v);
    dp[u].push_front(dp[u][0]);

    if (dp[u].size() > d)
    {
        dp[u][0] = max(dp[u][0], dp[u][d] + 1);
    }

    for (int v : g[u])
    {
        if (v == big)
        {
            continue;
        }

        for (int mn_dist = 0; mn_dist <= dp[v].size(); mn_dist++)
        {
            int rem_dist = max(mn_dist, d - mn_dist);
            int opt1 = dp[u][mn_dist], opt2 = dp[u][mn_dist];

            if (dp[v].size() >= rem_dist && rem_dist >= 1)
            {
                opt1 += dp[v][rem_dist - 1];
            }

            if (dp[u].size() > rem_dist && mn_dist >= 1)
            {
                opt2 = dp[u][rem_dist] + dp[v][mn_dist - 1];
            }

            dp[u][mn_dist] = max(opt1, opt2);
        }

        for (int i = min(dp[v].size(), dp[u].size() - 2); i >= 0; i--)
        {
            dp[u][i] = max(dp[u][i], dp[u][i + 1]);
        }
    }
}

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

    cin >> n >> d;

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

        cin >> p;

        g[p].push_back(i);
    }

    dfs(0);

    cout << dp[0][0] << endl;

    return 0;
}

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