제출 #1210208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210208		Ludissey	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	99 ms	35264 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;
        }
        vector<pair<int,int>> vc;
        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,(int)(dp[0]->size()-k-1));
            vc.push_back({dp[0]->size()-(mn+1),kmx+(*dp[i])[j]});
        }
        for (int j = (int)dp[i]->size()-1; j >=max(0,(int)dp[i]->size()-d); j--){
            int v=dp[i]->size()-j;
            k=dp[0]->size()-max(v,d-v)-1;
            if(k>=0) vc.push_back({dp[0]->size()-(v+1),(*dp[0])[k]+(*dp[i])[j]});
        }
        for (int i = 0; i < sz(vc); i++)
        {
            (*dp[0])[vc[i].first]=max((*dp[0])[vc[i].first],vc[i].second);
        }
    }
    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]);
    if((int)dp[0]->size()>1) (*dp[0])[dp[0]->size()-1]=max((*dp[0])[dp[0]->size()-1],(*dp[0])[dp[0]->size()-2]);
    /*cerr << "DP OF " << x<< ": ";
    for (int j = 0; j < (int)dp[0]->size(); j++)
    {
        cerr << (*dp[0])[j] << " ";
    }
    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: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49