Submission #1060210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060210		gyg	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1047 ms	15052 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 2e5 + 5;
 
int n, k;
array<vector<int>, MAX_N> adj;
 
array<bool, MAX_N> seen1;
array<int, MAX_N> depth;
void dfs1(int u) {
    seen1[u] = true;
    for (int v : adj[u])
        if (!seen1[v]) depth[v] = depth[u] + 1, dfs1(v);
}

array<bool, MAX_N> del;
array<bool, MAX_N> seen2;
void dfs2(int u, int d = 0) {
    seen2[u] = true, del[u] = true;
    if (d == k - 1) return;
    for (int v : adj[u])
        if (!seen2[v]) dfs2(v, d + 1);
}
 
array<pii, MAX_N> order;
int comp() {
    for (int u = 1; u <= n; u++) order[u] = {depth[u], u};
    sort(order.begin() + 1, order.begin() + n + 1, greater<pii>());

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int u = order[i].second;
        if (del[u]) continue;
        ans++;
        fill(seen2.begin(), seen2.end(), false), dfs2(u);
    }
    return ans;
}
 
int main() {
    // freopen("cat.in", "r", stdin);
    cin >> n >> k; 
    for (int u = 2; u <= n; u++) {
        int v; cin >> v; v++;
        adj[u].push_back(v), adj[v].push_back(u);
    }
 
    dfs1(1);
    int ans = comp();
    cout << ans << '\n';
}

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