oj.uz

답안 #360008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360008 2021-01-27T11:58:26 Z Pety Cat in a tree (BOI17_catinatree) C++14
0 / 100
 124 ms 139676 KB 
#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], 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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 139676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 139676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 139676 KB Output isn't correct
2 Halted 0 ms 0 KB -