Submission #360053

#	Time	Username	Problem	Language	Result	Execution time	Memory
360053		Pety	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	462 ms	244536 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

int n, d, child[200002], second[200002], height[200002], Max[200002];
vector<int>G[200002];
deque<int>dp[200002];

void calc (int nod) {
  for (int it : G[nod]) {
    calc(it);
    if (height[nod] < height[it] + 1) {
      child[nod] = it;
      second[nod] = height[nod];
      height[nod] = height[it] + 1;
    }
    else if (second[nod] < height[it] + 1)
      second[nod] = height[it] + 1;
  }
}

void dfs1 (int nod) {
  for (auto it : G[nod])
    dfs1(it);
  for (int i = 0; i <= second[nod]; i++)
    Max[i] = 0;
  for (auto it : G[nod])
    for (int j = 1; j <= min(height[it] + 1, min(second[nod], d / 2)); j++)
      Max[j] = max(Max[j], dp[it][j - 1] - ((d - j - 1 <= height[it]) ? dp[it][d - j - 1] : 0));
  int dp0 = 1;
  for (auto it : G[nod])
    if (height[it] >= d - 1)
      dp0 += dp[it][d - 1];
  if (child[nod])
    swap(dp[nod], dp[child[nod]]);
  dp[nod].push_front(dp0);
  for (auto it : G[nod])
    if (it != child[nod])
      for (int j = 1; j <= min(height[it] + 1, d - 1); j++)
        dp[nod][j] += dp[it][j - 1];
  for (int j = 1; j <= min(d / 2, second[nod]); j++)
    dp[nod][j] = ((d - j <= height[nod]) ? dp[nod][d - j] : 0) + Max[j];
  for (int j = second[nod]; j >= 0; j--)
    if (j + 1 <= height[nod])
      dp[nod][j] = max(dp[nod][j + 1], dp[nod][j]);
}




int main()
{
  cin >> n >> d;
  int x;
  for (int i = 2; i <= n; i++) {
    cin >> x;
    x++;
    G[x].push_back(i);
  }
  calc(1);
  dfs1(1);
  cout << dp[1][0];
  return 0;
}

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