Submission #1280478

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

catinatree

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    int D;
    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);
    }

    // محاسبه parent و depth با BFS از ریشه 0
    vector<int> parent(N, -1), depth(N, 0);
    queue<int> q;
    q.push(0);
    parent[0] = -1;
    depth[0] = 0;
    int maxDepth = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            maxDepth = max(maxDepth, depth[u]);
            q.push(u);
        }
    }

    // لیستِ رئوس به ازای هر عمق (برای گرفتن عمیق‌ترین غیرحذف‌شده)
    vector<vector<int>> byDepth(maxDepth + 1);
    for (int v = 0; v < N; ++v) byDepth[depth[v]].push_back(v);

    vector<char> removed(N, false);
    int curDepth = maxDepth;
    int answer = 0;

    while (true) {
        // پیدا کردن عمیق‌ترین راسی که هنوز موجود و غیرحذف‌شده است
        while (curDepth >= 0) {
            while (!byDepth[curDepth].empty() && removed[byDepth[curDepth].back()]) byDepth[curDepth].pop_back();
            if (!byDepth[curDepth].empty()) break;
            --curDepth;
        }
        if (curDepth < 0) break;

        int v = byDepth[curDepth].back();
        byDepth[curDepth].pop_back();
        if (removed[v]) continue;

        // علامت زدن این راس
        ++answer;

        // حذف همه رئوسی که تا فاصله D-1 از v هستند (BFS محدود)
        if (D == 0) continue; // در صورت غیرعادی، ولی طبق صورت سوال D>=1 است
        queue<pair<int,int>> qq;
        removed[v] = true;
        qq.push({v, 0});
        int limit = D - 1;
        while (!qq.empty()) {
            auto [x, dist] = qq.front(); qq.pop();
            if (dist == limit) continue;
            for (int nb : adj[x]) {
                if (!removed[nb]) {
                    removed[nb] = true; // بلافاصله حذف می‌کنیم تا دوباره enqueue نشود
                    qq.push({nb, dist + 1});
                }
            }
        }
    }

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

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