oj.uz

Submission #357717

# Submission time Handle Problem Language Result Execution time Memory
357717 2021-01-24T13:39:45 Z spatarel Cat in a tree (BOI17_catinatree) C++17
100 / 100
 353 ms 245100 KB 
#include <stdio.h>
#include <algorithm>
#include <deque>
#include <vector>

const int MAX_N = 200000;

int N, D;
std::vector<int> children[MAX_N];

std::deque<int> maxN[MAX_N];
int depth[MAX_N];

void dfs(int u) {
  depth[u] = 1;
  int deepestChild = -1;
  int secondDepth = 0;
  for (int v : children[u]) {
    dfs(v);
    if (depth[u] <= 1 + depth[v]) {
      secondDepth = depth[u];
      depth[u] = 1 + depth[v];
      deepestChild = v;
    } else if (secondDepth < 1 + depth[v]) {
      secondDepth = 1 + depth[v];
    }
  }
  
  std::vector<int> maxAdd(secondDepth);
  for (int v : children[u]) {
    for (int d = 0; d < D - d - 2 && d < depth[v] && d + 1 < secondDepth; d++) {
      maxAdd[d + 1] = std::max(maxAdd[d + 1],
          maxN[v][d] - (D - d - 2 < depth[v] ? maxN[v][D - d - 2] : 0));
    }
  }
  int maxNU0 = 1;
  for (int v : children[u]) {
    if (depth[v] > D - 1) {
      maxNU0 += maxN[v][D - 1];
    }
  }
  if (deepestChild != -1) {
    std::swap(maxN[u], maxN[deepestChild]);
  }
  maxN[u].push_front(maxNU0);
  for (int v : children[u]) {
    if (v != deepestChild) {
      for (int d = 0; d < D && d < depth[v]; d++) {
        maxN[u][d + 1] += maxN[v][d];
      }
    }
  }
  for (int d = 0; d + 1 < secondDepth && d < D - d - 2; d++) {
    maxN[u][d + 1] = maxAdd[d + 1] + (D - d - 1 < depth[u] ? maxN[u][D - d - 1] : 0);
  }
  for (int d = secondDepth; d >= 1; d--) {
    maxN[u][d - 1] = std::max(maxN[u][d - 1], maxN[u][d]);
  }
  /*
  printf("maxN[%d] = {", u);
  for (int d = 0; d < D && d < depth[u]; d++) {
    printf("%d, ", maxN[u][d]);
  }
  printf("}\n");
  fflush(stdout);//*/
}

int main() {
  scanf("%d%d", &N, &D);
  for (int i = 1; i < N; i++) {
    int xi;
    scanf("%d", &xi);
    children[xi].push_back(i);
  }
  dfs(0);
  int answer = maxN[0][0];
  printf("%d\n", answer);
  return 0;
}

Compilation message

catinatree.cpp: In function 'int main()':
catinatree.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d%d", &N, &D);
      |   ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d", &xi);
      |     ~~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 139628 KB Output is correct
2 Correct 99 ms 139628 KB Output is correct
3 Correct 101 ms 139756 KB Output is correct
4 Correct 99 ms 139628 KB Output is correct
5 Correct 99 ms 139756 KB Output is correct
6 Correct 100 ms 139628 KB Output is correct
7 Correct 111 ms 139628 KB Output is correct
8 Correct 100 ms 139756 KB Output is correct
9 Correct 99 ms 139628 KB Output is correct
10 Correct 100 ms 139756 KB Output is correct
11 Correct 99 ms 139756 KB Output is correct
12 Correct 102 ms 139720 KB Output is correct
13 Correct 100 ms 139756 KB Output is correct
14 Correct 98 ms 139628 KB Output is correct
15 Correct 99 ms 139628 KB Output is correct
16 Correct 100 ms 139648 KB Output is correct
17 Correct 99 ms 139652 KB Output is correct
18 Correct 100 ms 139628 KB Output is correct
19 Correct 102 ms 139776 KB Output is correct
20 Correct 99 ms 139628 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 139628 KB Output is correct
2 Correct 99 ms 139628 KB Output is correct
3 Correct 101 ms 139756 KB Output is correct
4 Correct 99 ms 139628 KB Output is correct
5 Correct 99 ms 139756 KB Output is correct
6 Correct 100 ms 139628 KB Output is correct
7 Correct 111 ms 139628 KB Output is correct
8 Correct 100 ms 139756 KB Output is correct
9 Correct 99 ms 139628 KB Output is correct
10 Correct 100 ms 139756 KB Output is correct
11 Correct 99 ms 139756 KB Output is correct
12 Correct 102 ms 139720 KB Output is correct
13 Correct 100 ms 139756 KB Output is correct
14 Correct 98 ms 139628 KB Output is correct
15 Correct 99 ms 139628 KB Output is correct
16 Correct 100 ms 139648 KB Output is correct
17 Correct 99 ms 139652 KB Output is correct
18 Correct 100 ms 139628 KB Output is correct
19 Correct 102 ms 139776 KB Output is correct
20 Correct 99 ms 139628 KB Output is correct
21 Correct 99 ms 140012 KB Output is correct
22 Correct 108 ms 139756 KB Output is correct
23 Correct 101 ms 139756 KB Output is correct
24 Correct 112 ms 139884 KB Output is correct
25 Correct 111 ms 139884 KB Output is correct
26 Correct 108 ms 139884 KB Output is correct
27 Correct 110 ms 140012 KB Output is correct
28 Correct 110 ms 140012 KB Output is correct
29 Correct 109 ms 140140 KB Output is correct
30 Correct 109 ms 140012 KB Output is correct
31 Correct 110 ms 140140 KB Output is correct
32 Correct 109 ms 140396 KB Output is correct
33 Correct 111 ms 140396 KB Output is correct
34 Correct 110 ms 140396 KB Output is correct
35 Correct 109 ms 140524 KB Output is correct
36 Correct 110 ms 140396 KB Output is correct
37 Correct 109 ms 140396 KB Output is correct
38 Correct 110 ms 140396 KB Output is correct
39 Correct 111 ms 140268 KB Output is correct
40 Correct 102 ms 139884 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 139628 KB Output is correct
2 Correct 99 ms 139628 KB Output is correct
3 Correct 101 ms 139756 KB Output is correct
4 Correct 99 ms 139628 KB Output is correct
5 Correct 99 ms 139756 KB Output is correct
6 Correct 100 ms 139628 KB Output is correct
7 Correct 111 ms 139628 KB Output is correct
8 Correct 100 ms 139756 KB Output is correct
9 Correct 99 ms 139628 KB Output is correct
10 Correct 100 ms 139756 KB Output is correct
11 Correct 99 ms 139756 KB Output is correct
12 Correct 102 ms 139720 KB Output is correct
13 Correct 100 ms 139756 KB Output is correct
14 Correct 98 ms 139628 KB Output is correct
15 Correct 99 ms 139628 KB Output is correct
16 Correct 100 ms 139648 KB Output is correct
17 Correct 99 ms 139652 KB Output is correct
18 Correct 100 ms 139628 KB Output is correct
19 Correct 102 ms 139776 KB Output is correct
20 Correct 99 ms 139628 KB Output is correct
21 Correct 99 ms 140012 KB Output is correct
22 Correct 108 ms 139756 KB Output is correct
23 Correct 101 ms 139756 KB Output is correct
24 Correct 112 ms 139884 KB Output is correct
25 Correct 111 ms 139884 KB Output is correct
26 Correct 108 ms 139884 KB Output is correct
27 Correct 110 ms 140012 KB Output is correct
28 Correct 110 ms 140012 KB Output is correct
29 Correct 109 ms 140140 KB Output is correct
30 Correct 109 ms 140012 KB Output is correct
31 Correct 110 ms 140140 KB Output is correct
32 Correct 109 ms 140396 KB Output is correct
33 Correct 111 ms 140396 KB Output is correct
34 Correct 110 ms 140396 KB Output is correct
35 Correct 109 ms 140524 KB Output is correct
36 Correct 110 ms 140396 KB Output is correct
37 Correct 109 ms 140396 KB Output is correct
38 Correct 110 ms 140396 KB Output is correct
39 Correct 111 ms 140268 KB Output is correct
40 Correct 102 ms 139884 KB Output is correct
41 Correct 240 ms 184016 KB Output is correct
42 Correct 222 ms 168028 KB Output is correct
43 Correct 225 ms 168044 KB Output is correct
44 Correct 220 ms 168172 KB Output is correct
45 Correct 219 ms 168008 KB Output is correct
46 Correct 348 ms 196716 KB Output is correct
47 Correct 353 ms 196588 KB Output is correct
48 Correct 349 ms 196588 KB Output is correct
49 Correct 350 ms 196588 KB Output is correct
50 Correct 193 ms 192236 KB Output is correct
51 Correct 195 ms 192236 KB Output is correct
52 Correct 192 ms 192108 KB Output is correct
53 Correct 286 ms 245100 KB Output is correct
54 Correct 286 ms 245100 KB Output is correct
55 Correct 281 ms 245100 KB Output is correct
56 Correct 112 ms 140556 KB Output is correct
57 Correct 118 ms 144236 KB Output is correct
58 Correct 154 ms 163180 KB Output is correct
59 Correct 279 ms 212460 KB Output is correct
60 Correct 234 ms 179048 KB Output is correct
61 Correct 248 ms 178412 KB Output is correct