Submission #1048188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048188		duckindog	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	6 ms	13144 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

const int N = 2'000 + 10;
int n, d;
vector<int> ad[N];

int f[N][N], maxV[N], maxU[N];
void dfs(int u, int p = -1) { 
  f[u][0] = 1;
  for (const auto& v : ad[u]) { 
    dfs(v, u);
    for (int i = d; i >= 0; --i) {
      maxU[i] = max(f[u][i], maxU[i + 1]);
      maxV[i] = max(f[v][i], maxV[i + 1]);
    }
    for (int i = 0; i <= d; ++i) { 
      auto& ret = f[u][i];
      ret = max(ret, f[u][i] + maxV[max(i, d - i - 1)]);
      if (i) ret = max(ret, f[v][i - 1] + maxU[max(i, d - i)]);
    }
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> d;
  for (int v = 1; v < n; ++v) { 
    int u; cin >> u;
    ad[u].push_back(v);
  }

  dfs(0);
  cout << *max_element(f[0], f[0] + d + 1) << "\n";
}

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