Submission #1048193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048193		duckindog	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	50 ms	15452 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, d;
vector<int> ad[N];

int depth[N];
int a[N];
void dfs(int u, int x) { 
  if (a[u] >= x) return;
  a[u] = x;
  for (const auto& v : ad[u]) dfs(v, x - 1);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> d;
  for (int v = 1; v < n; ++v) { 
    int u; cin >> u;
    ad[u].push_back(v);
    ad[v].push_back(u);
    depth[v] = depth[u] + 1;
  }

  int answer = 0;
  vector<int> vt(n); iota(vt.begin(), vt.end(), 0);
  sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
    return depth[a] > depth[b];
  });
  for (const auto& i : vt) { 
    answer += !a[i];
    if (!a[i]) dfs(i, d);
  }

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

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