Submission #1215079

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

catinatree

#include <bits/stdc++.h>
using namespace std;

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

    int n, d;
    cin >> n >> d;

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

    // 1) BFS from root to compute depth & parent, and collect nodes by depth
    vector<int> depth(n), parent(n);
    queue<int> q;
    q.push(0);
    parent[0] = -1;
    depth[0] = 0;
    int maxDepth = 0;
    vector<vector<int>> buckets(n);
    while(!q.empty()){
        int u = q.front(); q.pop();
        maxDepth = max(maxDepth, depth[u]);
        buckets[depth[u]].push_back(u);
        for(int v : adj[u]){
            if(v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }

    // 2) Greedy: always pick the deepest remaining node,
    //    then remove it and all nodes within distance < d via a small BFS.
    vector<char> removed(n, false), seen(n, false);
    vector<int> bfsVisited;
    bfsVisited.reserve(n);

    int currDepth = maxDepth;
    int answer = 0;

    while(true){
        // find the next deepest unused node
        while(currDepth >= 0 && buckets[currDepth].empty())
            currDepth--;
        if(currDepth < 0) break;

        int u = buckets[currDepth].back();
        buckets[currDepth].pop_back();
        if(removed[u]) continue;

        // pick u
        answer++;

        // BFS from u up to distance d-1, marking seen[]
        bfsVisited.clear();
        queue<pair<int,int>> bfsQ;
        seen[u] = 1;
        bfsVisited.push_back(u);
        bfsQ.emplace(u, 0);

        while(!bfsQ.empty()){
            auto [v, distv] = bfsQ.front(); bfsQ.pop();
            if(distv == d - 1) continue;
            for(int w : adj[v]){
                if(!seen[w] && !removed[w]){
                    seen[w] = 1;
                    bfsVisited.push_back(w);
                    bfsQ.emplace(w, distv + 1);
                }
            }
        }

        // remove all seen nodes and reset seen[]
        for(int v : bfsVisited){
            removed[v] = 1;
            seen[v] = 0;
        }
    }

    cout << answer << "\n";
    return 0;
}

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