Submission #1275579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275579		rtri	Cat in a tree (BOI17_catinatree)	C++20	11 / 100	2 ms	648 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());
  vector<int> pref(c.size() + 1);
  for (int i = 0; i < c.size(); i++)
    pref[i + 1] = pref[i] + c[i].second;

  int ans = 0, length = d;
  for (int i = 0; i < c.size(); i++) {
    int a = c[i].second;
    for (int j = i + 1; j < c.size(); j++) {
      if (d <= c[j].first + c[i].first)
        a += c[j].second;
      else
        break;
    }

    // cerr << "RES  " << i << " " << a << endl;
    if (ans < a || (ans == a && c[i].first > length)) {
      length = c[i].first;
      ans = a;
    }
  }

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

  // cerr << "NODE " << u << " " << ans << " " << length << endl;
  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: 11 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49