Submission #1361021

#TimeUsernameProblemLanguageResultExecution timeMemory
1361021po_rag526Cat in a tree (BOI17_catinatree)C++20
100 / 100
60 ms22136 KiB
//#include <bits/stdc++.h>
#include <random>
#include "set"
#include <iostream>
#include "vector"
#include "deque"
#include "climits"
#include "algorithm"
#include "stack"
#include "map"
#include "unordered_set"
#include "bitset"
#include "unordered_map"
#include "stack"
#include "queue"


using namespace std;

/*
            ====================================================================================================
            #*###*############*####*#####*####*############*#########################################*##########
            %%%%%%%%%###%##*##=*+++=+++++++++++++*@#@%%###%%%%%%%%%%%%%%%%%%%%@%@@@%@@@@@@@@@@@@@%%%%%%%@@@%%%%#
            %%%%%%%%%%#####*##=*++++++++++++++++=*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%@@@@@@@@%%%@@%%@@@%%%%#
            %%%%%%%%%######*##=*+++++++++++++++++*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%@@@@@@@@@%%#%%%%@@%#%#%#
            %%%%%%%%%%%####*##=*++++++++++++++++=+@%@%%###%@@@%%%%%%%%%%%%%%%%%%%%%%%@@%%%%@@@@@%%@%%%%%@%%%####
            %%%%%%%%%%####%*##=*++++++++++++++++=+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@%@@@%%%%%@%######
            %%%%%%%%%%####%*##=*++++++++++++++===+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%@@@@%#@%%%%%%@%#######
            %%%%%%%%%%#####*##+++++++++++=++++=+++@%#%##%#######%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@#%%%%%%@########
            %%%%%%%%%%#####*##+*+++++++++++++++==@%%%%%@##:-%=-=-+@%%%%%%%%%%%%%%%%%%%%%%%@@%%%@@@%%%%%@%%######
            %%%%%%%%%%#####*##+*++++++++++++=+*%%%%%%%%#%*.@:-%+-++%%%%%%%%%%%%%%%%%%%@%%%@%%%%%%%%%%%@@%#######
            %%%%%%%%%%####%*##=*=++++++++++++@%%%%%%%%%%%%#@@@@@@@=-@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@#######
            %%%%%%%%%%####%*##+*++++++++++++%@%%@%%%%%%%%#%@###*#%%@@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##+*+++++++++==@@%@@@@%%@%###%#@#=%@@@@@@@#=+@%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##*++++++++++++@@@@@@%#%%%%@#@@@@@@@@@@@@@@@@@-#%%%%%%%%%%%%%%@%%%%%%%%%%@@@%%%#####
            %%%%%%%%%#########=*++++++++++@@@@@%#@@@%%@@@@@@@@@@@@@@@@@@@@%@%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%#####
            %%%%%%%%######%*##=*++++++++++@%%@@@@@@@@@%%%####%@@%%%%@@@@@@@%#%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%#####
            %%%%%%%%##########=*++++++***#%%@@@@@@%%##*++++++***#*++*#%@@@@%%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%####
            %%%%%%%%######%###=*++++++#@%%@%@@@@%#*+++++====++++++++++*#@@@@%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%###
            %%%%%%%%######%###=*++++*%%%%@@@@@@@#+++++++=========++++++*#@@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%####
            %%%%%%%%%#####%###=*++**%@#@@@@@@@@%+++=================++++*@@@@%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#########=*+*#*@%@@@@@@%@%*++*+**##*++======*####*#*%@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%%########=#+*@%@@@@@@%@@@#*+=-=****#*+=+++=**#**#*+*#%@@%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###
            %%%%%%%%%%########+#*#@@@@%%%@@@%%#*+++*+=##+#*+*++##*+%**#**#%@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%%########=#**@@@@@@@@@@@@#*+=+=+++++++*==+*#*****++*#%%@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%#########=#**@@@@@@@@@@@@#*+===++++==+=+++**++=++++#%@@@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#####%###=##%@@@@@@@@@@@@#**+========++====++==+++*#%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##
            %%%%%%%#%#########+#+%@%#@@@@@@@@@%**+========+++===*++++++#%@@@%@%%%%%%%%@%%%%@%%%%%%%%%%%%%%%%####
            %%%%%%%%%%%#######=#+@@@@@@@@@@@@@#**++===+++****#**##*+++*%%@@@@@@%%%%@@@@@@@@@@@%%%%%%%%%%%%%%####
            @%%%%%##%%########+***@@@@@@@@@@@%#***++++*****#%###%%****#%@@@@%@%%%%%%%%%%%%%%%%%%%%%%%%#%%%%%%@@@
            %%%%%%%#%##%%%%###+**##%#@@@@@@@###***+++++++++++++*******#@@@@@@%%#%%%%%%%%%%%@%%%%%%%%%%%%%%%%%##%
            #@##%%##%##%######+**+++*@%##%%%%*********+++++++**********@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##%
            %@##%#%%%####%####+#*+*+++++++++#%**************************#%#*#%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%#%%%#
            @%%###%#%########*++===========++#@*++******##########******#++======@%%%%%%%%@%%%%%%%%%%%%%%%%%#%%#
            %%%##%##%##%###*++=========+=++++++*#********######*******+*=+==--=====*%%%#%%@%%%%%%%%%%%%%%%@%%%%#
            %%%##%%#%#####+++++*+=========+==+++**#******#####*******+*+++++==:======*%#%%@%%%%%%%%%%%%%%%%%%%#%
            %%%##%%%%#++==========--=----====+++++*##*****###*****+++#*===--+=====-------+**#@@%%%%%%%%%%%%%%%%%
            %#%%%+*++==========-=--=---------========++*@********+=%#===========----------======+@%%%%%%%%%%%%%%
            %#%***++========----------------------======++@.+++++*+==========---------------=-=====@%%%%%%%%%%%%
            %%**+++=========------------=---------=======+++*+*+%++========------------------==-====%%%%%%%%%%%%
            %**++++=========--===-=--=======------===========#*++============---------====----======+*%%%%%%%%%%
            #**+++++====+============+++++========-===========+*==============--=====+++++=====+===+=+*%%%%%%%%%
            #****+++==++++=====++++++****+++++===--=========+++++++=================+++***+++++++++++++%%%%%%%%%
            #*****+++++++++++++++++***##***++===-=---=======++*=*++++==============++++**#***+++++++++*+%%%%%%%%
            #******++++***++++++***######*+=====-----=--====++*+**+++======-=--=======+*#*##***+*+****#+@@%%%%%%
            ##********+**********####%%%+++++=====-----=====++*+***+++================++*#%####*********%@%+%%%%
            ###***************######%%#**++++++=============++++*#*+++======-========++++*%%####******#*%@@%%%%%
            ####****************##%%@#***++++++++++=========+++*=**++==============++++++**%%###*********#%%*%%%
            *****************+====*%%*********+++++===+====+++++++**++==+=*=====+++++++****@##++++=+****++*@%%%%
            *************+++=====--=@************+++++++++++++++******+++++++++++++++******#*+=====+++++*+++@%%%
            ***+++++*++++++=========+########**#%%*******++******%##***+++*++++++++++*******++++====++=++++**%%%
            ***+++========++========+%######*%###%#**************%###***************########***++++++++++++**#%%
            ***+++++++=====+++====+++*@#####%%%%%%######********#######**********###%%%%##%#**#*+++++==+++++**%%
            ***++++++++=======++++++**@%#######################%*#%%%#################%%#%%##**#*+++++++++++***%
            ***+++++**+++==========+*+#%%#######################**#%%###################%@%###*##*++++*+++++***%
            ****+**+++++++=======++*#*#@%%%%%%%%###########%%%#*****##%#%###########%%%%@%%%######+++++++++++***
            #*****+++++++++=====+++***#%%%%%%%%%%%%%%%%%%%%%%**++===+*#%%%%%%%%%%%%%%%%%@@%%#######*++++===+++**
            #*****+++++++=======+++**#%%%%%%%##############*+++==-===++*####%%%%%%##%%%%@@%%%######**+=====+++**
            ##****+++++++=====+*++***#%%%%%%%###########***++++++++++=++**############%%%%%%%%####****#*+=++++**
            ====================================================================================================
*/



using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
#define _ << ' ' <<
#define clearvis for (int i=0; i<maxn;visited[i++]=false)
//__int128 fpow(ll base,ll exp){__int128 result=1;while (exp){if (exp%2==1) result*=base;exp/=2;base*=base;}return result;}
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 */

ll fastpow(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1)
            res *= base;
        base *= base;
        res %= MOD;
        base %= MOD;
        exp >>= 1;
    }

    return res;
}

ll n, d;
vll edges[200005];
ll depth[200005];
vll byd[200005];
ll rmvd[200005];

void rmv(ll node, ll dist = d){
    if (rmvd[node] >= dist) return;

    rmvd[node] = dist;
    if (dist == 1) return;
    for (ll nd : edges[node]){
        rmv(nd, dist-1);
    }

}

void solve() {
    // cout << fixed << setprecision(6);
    ll ans = 0;
    cin >> n >> d;
    pb(byd[0], 0);
    for (int i=1; i<n; i++){
        ll x; cin >> x;
        depth[i] = depth[x] + 1;
        pb(byd[depth[i]], i);
        pb(edges[i],x);
        pb(edges[x], i);
    }
    for (int dep = n+2; dep >=0; dep--){
        for (ll node : byd[dep]){
            if (rmvd[node]) continue;
            rmv(node);
            ans++;
        }
    }

    cout << ans;
}


signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    //freopen("berries.in","r",stdin);
    //freopen("berries.out","w",stdout);
    ll t=1;
    //cin >> t;
    for (int i=1; i<=t; i++){
        //cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }
 

    return 0; // ok
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...