제출 #533002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533002		Stickfish	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	1 ms	460 KiB

catinatree

#include <iostream>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>
#include <set>
using namespace std;

const int MAXN = 1580;
int depth[MAXN];
vector<int> edg[MAXN];
bitset<MAXN> bs;


signed main() {
    int n, d;
    cin >> n >> d;
    vector<pair<int, int>> vs;
    for (int i = 1; i < n; ++i) {
        int rt;
        cin >> rt;
        edg[rt].push_back(i);
        depth[i] = depth[rt] + 1;
        vs.push_back({depth[i], i});
        edg[i].push_back(rt);
    }
    sort(vs.begin(), vs.end());
    int ans = 0;
    while (vs.size()) {
        int v = vs.back().second;
        vs.pop_back();
        if (!bs[v]) {
            ++ans;
            queue<pair<int, int>> q;
            q.push({v, 0});
            bs[v] = 1;
            while (q.size()) {
                auto [u, t] = q.front();
                q.pop();
                if (t + 1 < d) {
                    for (auto w : edg[u]) {
                        if (!bs[w]) {
                            bs[w] = 1;
                            q.push({w, t + 1});
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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