Submission #1275542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275542		rtri	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	332 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

int n, d;
vector<vector<int>> adj;

pair<int, int> dfs(int u, int p = -1) {
  vector<pair<int, int>> c;
  for (int v : adj[u])
    if (v != p) {
      auto [ans, length] = dfs(v, u);
      c.push_back({length, ans});
    }
  sort(c.begin(), c.end());
  reverse(c.begin(), c.end());

  int ans = 0, length = d;
  for (auto [a, l] : c) {
    if (d <= l + length) {
      ans += a;
      length = l;
    } else
      break;
  }

  if (d <= length) {
    ans++;
    length = 0;
  }

  return {ans, length + 1};
}

int main() {
  cin >> n >> d;

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

  auto [ans, length] = dfs(0);

  cout << ans << endl;

  return 0;
}

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