Submission #404802

#	Time	Username	Problem	Language	Result	Execution time	Memory
404802		rama_pang	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	61 ms	11756 KiB

catinatree

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, D;
  cin >> N >> D;

  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    int p;
    cin >> p;
    adj[p].emplace_back(i);
  }

  // Solution:
  //
  // Similar to: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_h
  //
  // For each node, we save the maximum number of picked nodes, which
  // also maximizes the minimum distance to current node. We additionally save the
  // number of nodes which has that maximum minimum distance.
  //
  // Consider 2 children of current node. Assume from child[1], we pick 1 node,
  // where the distance is a, and from the other child, we pick 2 nodes, where
  // the distance to current node is p + x and q + x (distance between the 2 nodes
  // is p + q).
  //
  // Then, we have p + q >= K. Moreover, if:
  // a + x + p < K
  // a + x + q < K
  // p + q >= K
  // Implies:
  // 2a + 2x + (p + q) < 2K
  // 2a + 2x < K
  // a + x < K / 2
  //
  // Then, since p + q >= K -> max(p, q) >= K / 2
  //
  // So, a + x + p < K and a + x + q < K only happens when:
  // p = q = K / 2
  // a + x < K / 2
  //
  // If p > K / 2, then a + x + p >= K, so we using the
  // explained data (maximum picked, distance to picked,
  // count nodes with that distance) is enough.
  //
  // We can also note that, since p, q is from same child,
  // then x >= 1. So, this a + x + p < K and a + x + q < K
  // case can only happen when a < K / 2 - 1. But in this case,
  // we can just not pick a to preserve the condition (by picking
  // p and q) instead. So, we only need to keep the minimum distance
  // instead.
  //
  // Time complexity: O(N).

  int ans = 0;
  const auto Dfs = [&](const auto &self, int u) -> int {
    ans += 1; // pick current node
    int dist = 0;
    for (auto v : adj[u]) {
      int other = self(self, v) + 1;
      if (dist + other < D) {
        ans -= 1; // we only need to decrease 1, by lemma above
        dist = max(dist, other);
      } else {
        dist = min(dist, other);
      }
    }
    return dist;
  };

  Dfs(Dfs, 0);

  cout << ans << '\n';
  return 0;
}

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