Submission #1270421

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

catinatree

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

vvi G;
vi par, dep, blocked;
int ans = 0, d;

void dfs(int node, int p){
    dep[node] = (p == -1 ? 0 : dep[p] + 1);
    for(int nei : G[node]){
        if(nei == p) continue;
        dfs(nei, node);
    }
}

void mark(int node){
    if(blocked[node] != -1) return; // already covered
    ans++;
    queue<pii> q;
    q.push({node, d});
    while(!q.empty()){
        auto [u, dist] = q.front();
        q.pop();
        if(dist < 0) continue;
        if(blocked[u] >= dist) continue;
        blocked[u] = dist;
        for(int nei : G[u]){
            q.push({nei, dist-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);
    dfs(0, -1);

    blocked.assign(n, -1);

    vector<pair<int,int>> depths;
    for(int i=0; i<n; i++){
        depths.push_back({-dep[i], i});
    }
    sort(depths.begin(), depths.end());

    for(auto [negd, node] : depths){
        mark(node);
    }
    cout << ans << "\n";
}

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