제출 #1361012

#제출 시각아이디문제언어결과실행 시간메모리
1361012ibshaCat in a tree (BOI17_catinatree)C++20
0 / 100
2 ms344 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 par[200005];
ll depth[200005];
vll byd[200005];
bool visited[200005];

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

    visited[node] = true;
    for (ll nd : edges[node]){
        rmv(nd, dist-1);
    }

}

void solve() {
    // cout << fixed << setprecision(6);
    ll ans = 0;
    cin >> n >> d;
    for (int i=1; i<n; i++){
        ll x; cin >> x;
        par[i] = 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 (visited[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;
}

#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…