Submission #1270420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270420		Davdav1232	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	320 KiB

catinatree

// 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<int> 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-1});
    while(!q.empty()){
        vii x=q.front();
        q.pop();
        if(blocked[x.first]>=x.second){
            continue;
        }
        blocked[x.first]=x.second;
        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;
    dfs(0, 0);
    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;
}

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