Submission #1370624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370624		eradax	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	30 ms	14248 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,d;cin>>n>>d;
    vector<int>p(n);for(int i=1;i<n;i++)cin>>p[i];
    vector<vector<pair<int,int>>>ch(n);

    pair<int,int>a;
    for(int i=n-1;~i;i--){
        pair<int,int>r{1e9,0};
        ch[i].push_back({0,1});
        sort(rbegin(ch[i]),rend(ch[i]));
        for(auto[x,y]:ch[i])r.second+=y-1;
        for(auto[x,y]:ch[i])if(x+r.first>=d)r.first=x,r.second++;
        r.first++;
        ch[p[i]].push_back(a=r);
    }
    cout<<a.second<<'\n';
}

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