Submission #373246

#	Time	Username	Problem	Language	Result	Execution time	Memory
373246		ijxjdjd	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	4 ms	5100 KiB

catinatree

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;
const int MAXN = (int)(2e5);
bool blocked[MAXN];
int cnt[MAXN];
vector<int> adj[MAXN];
int ans = 0;
vector<int> pos;
void bk(int n, int d) {
    if (d == 0) {
        cnt[n]--;
        if (cnt[n] == 1) {
            pos.push_back(n);
        }
        return;
    }
    else {
        blocked[n] = true;
        for (int e : adj[n]) {
            if (!blocked[e]) {
                bk(e, d-1);
            }
        }
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, D;
	cin >> N >> D;
	FR(i, N-1) {
        int p;
        cin >> p;
        adj[i+1].push_back(p);
        cnt[i+1]++;
        adj[p].push_back(i+1);
        cnt[p]++;
	}
	FR(i, N) {
        if (cnt[i] == 1) {
            pos.push_back(i);
        }
	}
	while (pos.size()) {
        int nxt = pos.back();
        pos.pop_back();
        if (!blocked[nxt]) {
            ans++;
            bk(nxt, D);
        }
	}
	cout << ans << '\n';
	return 0;
}

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