Submission #1267605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267605		vnedu	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	702 ms	14140 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
#define TASK ""

const int N = 2e5 + 5;
int n,d;
vector<int> adj[N];
namespace sub12
{
    bool check()
    {
        return n<=1500;
    }
    const int N = 1500 + 5;
    int dp[N][N];
    void dfs(int u, int pa)
    {
        dp[u][0]=1;
        for(int v : adj[u])
        {
            if(v!=pa)
            {
                dfs(v,u);
                dp[u][0]+=dp[v][d-1];
                for(int j=1;j<=d;++j)
                {
                    for(int k=j;k<=d;++k)
                    {
                        dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][max(j-1,d-1-k)]);
                    }
                }
            }
        }
        dp[u][0]=max(dp[u][0],dp[u][1]);
    }
    void solve()
    {
        dfs(1,-1);
        int ans=0;
        for(int j=0;j<=d;++j)
        {
            ans=max(ans,dp[1][j]);
        }
        cout<<ans;
    }
}
void solve()
{
    cin>>n>>d;
    for(int i=2;i<=n;++i)
    {
        int u;
        cin>>u;
        ++u;
        adj[i].push_back(u);
        adj[u].push_back(i);
    }
    if(sub12::check())
    {
        return void(sub12::solve());
    }
}
int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int testcase=1;
//    cin>>testcase;
    while(testcase--)
        solve();
//    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

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