Submission #559091

#	Time	Username	Problem	Language	Result	Execution time	Memory
559091		Sweezy	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	208 ms	524288 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<int> p(n);
  vector<vector<int>> g(n);
  reps(i, 1, n) {
    cin >> p[i];
    g[p[i]].push_back(i);
  }

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

Compilation message (stderr)

catinatree.cpp: In lambda function:
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
catinatree.cpp:44:5: note: in expansion of macro 'debug'
   44 |     debug(v);
      |     ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
catinatree.cpp:47:7: note: in expansion of macro 'debug'
   47 |       debug(dist);
      |       ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
catinatree.cpp:65:5: note: in expansion of macro 'debug'
   65 |     debug(v, tr);
      |     ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
catinatree.cpp:73:5: note: in expansion of macro 'debug'
   73 |     debug(v, dp[v]);
      |     ^~~~~

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