Submission #1155997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155997		Ludissey	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	320 KiB

catinatree

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int n,d;
vector<vector<int>> neigh;

bool cmp(vector<int>* a, vector<int>* b){
    return a->size()>b->size();
}


vector<int> *dfs(int x, int p){
    vector<vector<int> *> dp;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        dp.push_back(dfs(u,x));
    }
    sort(all(dp),cmp);
    if(sz(dp)==0) {
        vector<int> *ep= new vector<int>();
        dp.push_back(ep);
    }
    dp[0]->push_back(1);
    for (int i = 1; i < sz(dp); i++)
    {
        for (int j = 0; j < (int)dp[i]->size(); j++)
        {
            int v=dp[i]->size()-j;
            int nv=(dp[0]->size()-(d-v))-1;
            if(nv<0) continue;
            (*dp[0])[max(v,nv)]=max((*dp[0])[max(v,nv)],(*dp[0])[nv]+(*dp[i])[j]);
        }
        
    }
    /*cerr << x << "\n";
    for (int i = 0; i < (int)dp[0]->size(); i++) cerr << (*dp[0])[i] << " ";
    cerr << "\n";*/
    return dp[0];
} 


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d;
    neigh.resize(n);
    for (int i = 1; i < n; i++)
    {
        int x; cin >> x;
        neigh[x].push_back(i);
        neigh[i].push_back(x);
    }
    vector<int> *dp=dfs(0,-1);
    int ans=0;
    for (int i = 0; i < (int)dp->size(); i++) ans=max(ans,(*dp)[i]);
    
    cout << ans << "\n";
    return 0;
}

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