Submission #719826

#TimeUsernameProblemLanguageResultExecution timeMemory
719826JohannCat in a tree (BOI17_catinatree)C++14
100 / 100
149 ms15056 KiB
#include <bits/stdc++.h>
using namespace std;

#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i, n) for (int i = 0; i < (n); ++i)

void dfs(vvi & adj, int v, int p, int d, vi & blocked) {
    if (blocked[v] >= d) return;
    blocked[v] = d;
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs(adj, u, v, d-1, blocked);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, D;
    cin >> n >> D;

    vvi adj(n);
    for (int i = 1, p; i < n; ++i) {
        cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }

    vi obh;
    vb visited(n, false);
    queue<int> q;
    q.push(0);
    while (!q.empty()){
        int v = q.front(); q.pop();
        visited[v] = true;
        obh.push_back(v);
        for (int u : adj[v]) {
            if (!visited[u]) q.push(u);
        }
    }

    vi blocked(n, 0);
    int ans = 0;
    for (int i = n-1; i >= 0; --i) {
        int v = obh[i];
        if (blocked[v] > 0) continue;
        // cout << "v: " << v << endl;
        ++ans;
        dfs(adj, v, v, D, blocked);
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...