Submission #1210148

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

catinatree

#include <bits/stdc++.h>
#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);
    int v=0;
    if(sz(dp)!=0&&(int)dp[0]->size()>=d) {
        v+=(*dp[0])[dp[0]->size()-d];
    }
    if(sz(dp)==0) {
        vector<int> *ep= new vector<int>();
        dp.push_back(ep);
    }
    dp[0]->push_back(v+1);
    for (int i = 1; i < sz(dp); i++)
    {
        int k=(dp[0]->size()-d)-1;
        int kmx=0;
        int dmx=0;
        for (int j = 0; j < (int)dp[i]->size(); j++) {
            dmx=max((*dp[i])[j],dmx);
            (*dp[i])[j]=dmx;
        }

        for (int j = (int)dp[i]->size()-1; j >=max(0,(int)dp[i]->size()-d); j--)
        {
            int v=dp[i]->size()-j;
            k++;
            if(k>=0) {
                kmx=max((*dp[0])[k],kmx);
                (*dp[0])[k]=kmx;
            }
            int mn=min(v,d-v);
            (*dp[0])[mn]=max((*dp[0])[mn],kmx+(*dp[i])[j]);
        }
        
    }
    if((int)dp[0]->size()>d) (*dp[0])[dp[0]->size()-d]=max((*dp[0])[dp[0]->size()-d],(*dp[0])[dp[0]->size()-d-1]);
    for (int j = 1; j < (int)dp[0]->size(); j++)
    {
        (*dp[0])[j]=max((*dp[0])[j-1],(*dp[0])[j]);
    }
    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