Submission #399593

#	Time	Username	Problem	Language	Result	Execution time	Memory
399593		iulia13	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	392 ms	244284 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;
const int nmax = 2e5 + 5;
int n, D;
deque <int> dp[nmax];
vector <int> g[nmax];
int depth[nmax], deep[nmax], second[nmax], maxim[nmax];
void precalc(int nod)
{
    for (auto x : g[nod])
    {
        precalc(x);
        if (depth[nod] < depth[x] + 1)
        {
            deep[nod] = x;
            second[nod] = depth[nod];
            depth[nod] = depth[x] + 1;
        }
        else
        if (second[nod] < depth[x] + 1)
            second[nod] = depth[x] + 1;
    }
}
void dfs(int nod)
{
    for (auto x : g[nod])
        dfs(x);
    for (int i = 0; i <= second[nod]; i++)
        maxim[i] = 0;
    for (auto x : g[nod])
        for (int d = 1; d <= min(depth[x] + 1, min(second[nod], D / 2)); d++)
        {
            if (D - d - 1 <= depth[x])
                maxim[d] = max(maxim[d], dp[x][d - 1] - dp[x][D - d - 1]);
            else
                maxim[d] = max(maxim[d], dp[x][d - 1]);
        }
    int dp0 = 1;
    for (auto x : g[nod])
        if (depth[x] >= D - 1)
            dp0 += dp[x][D - 1];
    if (deep[nod])
        swap(dp[nod], dp[deep[nod]]);
    dp[nod].push_front(dp0);
    for (auto x : g[nod])
        if (x != deep[nod])
            for (int d = 1; d <= min(depth[x] + 1, D - 1); d++)
                dp[nod][d] += dp[x][d - 1];
    for (int d = 1; d <= min(D / 2, second[nod]); d++)
    {
        if (D - d <= depth[nod])
            dp[nod][d] = dp[nod][D - d] + maxim[d];
        else
            dp[nod][d] = maxim[d];
    }
    for (int d = second[nod]; 0 <= d; d--)
        if (d + 1 <= depth[nod])
            dp[nod][d] = max(dp[nod][d + 1], dp[nod][d]);
}
int main()
{
    cin >> n >> D;
    for (int i = 1; i < n; i++)
    {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    precalc(0);
    dfs(0);
    cout << dp[0][0];
    return 0;
}

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