Submission #1098892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098892		ASN49K	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	1 ms	344 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int inf=1e9;
const int N=200'000;
int main()
{
    int n,dist;
    cin>>n>>dist;
    vector<int>p(n,0);

    vector<deque<int>>dp(n);
    for(auto &c:dp)
    {
        c.push_back(1);
    }
    for(int i=1;i<n;i++)
    {
        cin>>p[i];
    }
    for(int i=n-1;i>0;i--)
    {
        dp[i].push_front(0);
        if((int)dp[i].size()==dist+2)
        {
            dp[i].pop_back();
        }
        deque<int>&b=dp[i],&a=dp[p[i]];
        if(a.size()<b.size())
        {
            swap(a,b);
        }

        for(int i=0;i<(int)b.size();i++)
        {
            int remain=dist-i;
            int val=b[i];
            if(remain<(int)a.size())
            {
                val+=a[remain];
            }
            a[min(i,remain)]=max(a[min(i,remain)] , val);
        }
        for(int i=(int)b.size()-2;i>=0;i--)
        {
            a[i]=max(a[i],a[i+1]);
        }


    }
    cout<<dp[0][0];
    return 0;
}

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