Submission #559248

#	Time	Username	Problem	Language	Result	Execution time	Memory
559248		Sweezy	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1086 ms	42432 KiB

catinatree

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

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())

void solve() {
  int n, d;
  cin >> n >> d;
 
  if (d > n - 1) {
    cout << 1;
    return;
  }
 
  if (d == 0) {
    cout << n;
    return;
  }
 
  vector<vector<int>> g(n);
  reps(i, 1, n) {
    int p;
    cin >> p;
    g[p].push_back(i);
    g[i].push_back(p);
  }

  vector<int> s(n), used(n);
  function<void(int, int)> sizes = [&] (int v, int p) {
    s[v] = 1;
    for (auto &u : g[v]) {
      if (u != p && !used[u]) {
        sizes(u, v);
        s[v] += s[u];
      }
    }
  };

  function<int(int, int, int)> centroid = [&] (int v, int p, int n) {
    for (auto &u : g[v]) {
      if (u != p && !used[u] && s[u] > n / 2) {
        return centroid(u, v, n);
      } 
    }
    return v;
  };

  vector<vector<pair<int, int>>> centroids(n);
  function<void(int, int, int, int)> add_centroid = [&] (int v, int p, int centroid, int dist) {
    centroids[v].emplace_back(centroid, dist);
    for (auto &u : g[v]) {
      if (u != p && !used[u]) {
        add_centroid(u, v, centroid, dist + 1);
      }
    }
  };

  function<void(int)> decomposition1 = [&] (int v) {
    used[v] = 1;
    sizes(v, -1);

    add_centroid(v, -1, v, 0);

    for (auto &u : g[v]) {
      if (!used[u]) {
        decomposition1(centroid(u, v, s[u]));
      }
    }
  };
  decomposition1(0);

  int timer = 0;
  vector<pair<int, int>> vs;
  vector<int> tin(n), tout(n), par(n);
  function<void(int, int, int)> dfs = [&] (int v, int p, int dst) {
    par[v] = p;
    tin[v] = timer++;
    vs.emplace_back(dst, v);
    for (auto &u : g[v]) {
      if (u != p) {
        dfs(u, v, dst + 1);
      }
    }
    tout[v] = timer;
  };

  const int inf = 1e9;

  int res = 0;
  vector<int> mdist(n, inf);
  function<void(int)> decomposition2 = [&] (int v) {
    used[v] = 1;
    sizes(v, -1);

    vs.clear();
    dfs(v, -1, 0);
    sort(vs.begin(), vs.end());

    auto can = [&] (int ver, int dst) -> bool {
      for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
        if (dist_to_centroid + mdist[centroid] < d) {
          return false;
        }
      }
      return true;
    };

    int m = sz(vs), r = m, cnt = 0;
    rep(l, m) {
      while (r - 1 >= l && vs[r - 1].first >= max(vs[l].first, d - vs[l].first)) {
        r--;
        int ver = vs[r].second;
        int dst = vs[r].first;
        if (can(ver, dst)) {
          cnt++;
          for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
            mdist[centroid] = min(mdist[centroid], dist_to_centroid);
          }
        }
      }
      if (l == r) {
        res = max(res, cnt);
        break;
      } else {
        res = max(res, cnt + can(vs[l].second, vs[l].first));
      }
    }

    for (auto &[vd, ver] : vs) {
      for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
        mdist[centroid] = inf;
      }
    }

    for (auto &u : g[v]) {
      if (!used[u]) {
        decomposition2(centroid(u, v, s[u]));
      }
    }
  };

  used.assign(n, 0);
  decomposition2(0);

  cout << res;
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

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