oj.uz

Submission #559068

# Submission time Handle Problem Language Result Execution time Memory
559068 2022-05-09T10:41:17 Z Sweezy Cat in a tree (BOI17_catinatree) C++17
0 / 100
 1 ms 212 KB 
#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;
  d = min(d, n - 1);

  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) {
    dp[v][0] = 1;
    for (auto &u : g[v]) {
      dfs(u);
    }
    for (int dist = 1; dist <= d; dist++) {
      for (auto &u : g[v]) {
        int tr = dp[u][dist - 1];
        if (dist != d) {
          for (auto &w : g[v]) {
            if (w != u) {
              tr += dp[w][d - dist - 1];
            }
          }
        }
        dp[v][dist] = max(dp[v][dist], 1 + tr);
      }
    }
  };  
  dfs(0);

  int res = 0;
  rep(i, n) {
    res = max(res, dp[i][d]);
  }

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -