Submission #1270413

#TimeUsernameProblemLanguageResultExecution timeMemory
1270413Davdav1232Cat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms320 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> vii;
typedef vector<vii> vvii;

vvi G;
vi par;
vi dep;
vector<bool> blocked;
int ans=0;
int d;

void dfs(int node, int p){
    dep[node]=dep[p]+1;
    for(int i=0; i<G[node].size(); i++){
        if(G[node][i]==p) continue;
        dfs(G[node][i], node);
    }
}
void mark(int node){
    if(blocked[node]) return;
    ans++;
    queue<vii> q;
    q.push({node, d});
    while(!q.empty()){
        vii x=q.front();
        q.pop();
        if(blocked[x.first]){
            continue;
        }
        if(x.second==0){
            continue;
        }
        blocked[x.first]=1;
        for(int i=0; i<G[x.first].size(); i++){
            q.push({G[x.first][i], x.second-1});
        }
    }
}

int main() {
	int n;
    cin>>n>>d;
    par.resize(n);
    G.assign(n, {});
    for(int i=1; i<n; i++){
        cin>>par[i];
        G[i].push_back(par[i]);
        G[par[i]].push_back(i);
    }
    dep.resize(n);
    dep[0]=-1;
    blocked.assign(n, 0);
    vvii depths;
    for(int i=0; i<n; i++){
        depths.push_back({-dep[i], i});
    }
    sort(depths.begin(), depths.end());
    for(int i=0; i<n; i++){
        mark(depths[i].second);
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...