Submission #1299800

#TimeUsernameProblemLanguageResultExecution timeMemory
1299800aicloCat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms572 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long D; // D może być duże, użyjemy long long do obliczeń porównań
    if (!(cin >> N >> D)) return 0;
    vector<vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int p; cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }

    if (D <= 1) { // jeśli D==1 to dowolne 2 różne węzły mają odległość >=1 -> można zaznaczyć wszystkie
        cout << N << "\n";
        return 0;
    }

    // Oblicz głębokości od korzenia 0 (BFS)
    vector<int> depth(N, -1);
    queue<int> q;
    depth[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (depth[v] == -1) {
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }

    // Węzły posortowane malejąco po depth
    vector<int> nodes(N);
    for (int i = 0; i < N; ++i) nodes[i] = i;
    sort(nodes.begin(), nodes.end(), [&](int a, int b){
        return depth[a] > depth[b];
    });

    vector<char> blocked(N, 0); // zablokowany (nie można zaznaczyć)
    int answer = 0;
    int maxRadius = (int)(D - 1); // BFS radius do zablokowania (węzły o dist <= D-1)

    for (int u : nodes) {
        if (blocked[u]) continue;
        // zaznaczamy u
        ++answer;
        // blokujemy wszystkie węzły w odległości <= maxRadius od u
        queue<pair<int,int>> bfs;
        blocked[u] = 1;
        bfs.push({u, 0});
        while (!bfs.empty()) {
            auto [x, dist] = bfs.front(); bfs.pop();
            if (dist == maxRadius) continue;
            for (int y : adj[x]) {
                if (!blocked[y]) {
                    blocked[y] = 1;
                    bfs.push({y, dist + 1});
                }
            }
        }
    }

    cout << answer << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...