제출 #1098953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098953		ASN49K	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	59 ms	5688 KiB

catinatree

//nu am swap
#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(dp[i].front());
        if((int)dp[i].size()==dist+2)
        {
            dp[i].pop_back();
        }
        deque<int>&b=dp[i],&a=dp[p[i]];
        while(a.size()<b.size())
        {
            a.push_back(0);
        }
        map<int,int>new_dp;
        for(int i=b.size()-1;i>=0;i--)
        {
            int remain=dist-i;
            int val=b[i];
            if(remain<(int)a.size())
            {
                val+=a[remain];
            }
            new_dp[min(i,remain)]=max(new_dp[min(i,remain)] , val);
        }
        for(int i=(int)b.size()-1;i>=0;i--)
        {
            a[i]=max(a[i] , b[i]);
        }
        for(auto &c:new_dp)
        {
            a[c.first]=max(a[c.first] , c.second);
        }
        for(int i=(int)a.size()-2;i>=0;i--)
        {
            a[i]=max(a[i],a[i+1]);
        }


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

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