Submission #559221

#	Time	Username	Problem	Language	Result	Execution time	Memory
559221		Sweezy	Cat in a tree (BOI17_catinatree)	C++17	11 / 100	1088 ms	596 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())

struct Tree {
  typedef int T;
  static constexpr T unit = INT_MAX;
  T f(T a, T b) { return min(a, b); }
  vector<T> s; int n;
  Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
  void update(int pos, T val) {
    for (s[pos += n] = val; pos /= 2;)
      s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
  }
  T query(int b, int e) {
    T ra = unit, rb = unit;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) ra = f(ra, s[b++]);
      if (e % 2) rb = f(s[--e], rb);
    }
    return f(ra, rb);
  }
};

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);
  }

  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;
  };

  int res = 0;
  rep(root, n) {
    // debug(root);
    timer = 0;
    vs.clear();
    dfs(root, -1, 0);
    sort(vs.begin(), vs.end());
    // debug(vs);
    Tree st(n);
    int r = n, cnt = 0;

    auto can = [&] (int v, int dst) -> bool {
      bool ok = 1;
      int dv = 0;
      while (v != -1) {
        int dst_subtree = st.query(tin[v], tout[v]);
        ok &= dst_subtree - dst + dv >= d;
        dv++;
        dst--;
        v = par[v];
      }
      return ok;
    };

    rep(l, n) {
      while (r - 1 >= l && vs[r - 1].first >= max(vs[l].first, d - vs[l].first)) {
        r--;
        int v = vs[r].second;
        int dst = vs[r].first;
        if (can(v, dst)) {
          cnt++;
          st.update(tin[v], dst);
        }
      }
      // debug(l, r, cnt);
      if (l == r) {
        res = max(res, cnt);
        break;
      } else {
        res = max(res, cnt + can(vs[l].second, vs[l].first));
      }
    }
    // debug(res);
  }
 
  // vector<vector<int>> dp(n, vector<int> (n));
  // function<void(int)> dfs = [&] (int v) {
  //   for (auto &u : g[v]) {
  //     dfs(u);
  //   }
  //   debug(v);
  //   // v is off
  //   for (int dist = 1; dist <= d; dist++) {
  //     debug(dist);
  //     for (auto &u : g[v]) {
  //       int tr = dp[u][dist - 1];
 
  //       int other = max(dist, d - dist);
  //       for (auto &w : g[v]) {
  //         if (w != u) {
  //           tr += dp[w][other - 1];
  //         }
  //       }
  //       dp[v][dist] = max(dp[v][dist], tr);
  //     }
  //   }
  //   // v is on
  //   int tr = 0;
  //   for (auto &u : g[v]) {
  //     tr += dp[u][d - 1];
  //   }
  //   debug(v, tr);
  //   dp[v][0] = max(dp[v][0], 1 + tr);
  //   for (int dist = d - 1; dist >= 0; dist--) {
  //     dp[v][dist] = max(dp[v][dist], dp[v][dist + 1]);
  //   }
  //   // reps(dist, 1, n) {
  //   //   dp[v][dist] = max(dp[v][dist], dp[v][dist - 1]);
  //   // }
  //   debug(v, dp[v]);
  // };  
  // dfs(0);
 
  // int res = 0;
  // rep(i, n) {
  //   rep(dist, d + 1) {
  //     res = max(res, dp[i][dist]);
  //   }
  // }
 
  cout << res;
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

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