Submission #1266440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266440		abcdxyz123	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	274 ms	243648 KiB

catinatree

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,k;
vector<int>adj[maxn];
void ckmax(int &x,int y){if(x<y)x=y;}
void Push(deque<int>&cur)
{
    if(cur.empty())cur.push_front(0);
    else cur.push_front(cur.front());
}
void Combine(deque<int>&root,deque<int>&child)
{
    if(child.size()>root.size())swap(root,child);
    deque<int>comb=child;
    for(int i=0;i<child.size();i++)
    {
        int j=max(k-i,i);
        if(child.size()>j)ckmax(comb[i],child[j]+root[i]);
        if(root.size()>j)ckmax(comb[i],child[i]+root[j]);
    }
    int suff=0;
    for(int i=(int)comb.size()-1;i>=0;i--)
    {
        ckmax(suff,comb[i]);
        ckmax(root[i],suff);
    }
}
deque<int>dp[maxn];
void dfs(int u)
{
    dp[u].push_back(1);
    for(int v:adj[u])
    {
        dfs(v);
        Push(dp[v]);
        Combine(dp[u],dp[v]);
    }
    //cout<<"+>"<<u<<'\n';
    //for(int i=0;i<dp[u].size();i++)cout<<dp[u][i]<<' ';
    //cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int v=1;v<n;v++)
    {
        int u;
        cin>>u;
        adj[u].push_back(v);
    }
    dfs(0);
    cout<<dp[0].front()<<'\n';
}

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