Submission #1305616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305616		ghos007	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	29 ms	30172 KiB

catinatree

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int MAXN = 2000;
int dp[MAXN][MAXN];
void dfs(int u,int p,vector <vector <int>> &g,int d) {
  dp[u][0] = 1;
  vector <int> perehod(MAXN);
  for (auto el : g[u]) {
    if (el == p)continue;
    dfs(el,u,g,d);
    perehod[0] = dp[u][0] + dp[el][d-1];
    for (int i = 1;i <= d;i++) {
      int v1 = max(d - i,i);
      perehod[i] = max(dp[u][i] + dp[el][v1 - 1],dp[u][v1] + dp[el][i-1]);
    }
    for (int i = d;i >= 0;i--) {
      dp[u][i] = perehod[i];
      if (i != d) {
        dp[u][i] = max(dp[u][i],dp[u][i+1]);
      }
    }
  }
}
void solve() {
  int n,d;
  cin >> n >> d;
  vector <vector <int>> g(n);
  d = min(n,d);
  for (int i = 1;i < n;i++) {
    int x;
    cin >> x;
    g[x].push_back(i);
  }
  dfs(0,-1,g,d);
  int best = 0;
  for (auto el : dp[0]) {
    best = max(best,el);
  }
  cout << best << "\n";
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}

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