oj.uz

Submission #716371

# Submission time Handle Problem Language Result Execution time Memory
716371 2023-03-29T19:33:24 Z manizare Cat in a tree (BOI17_catinatree) C++14
51 / 100
 11 ms 9456 KB 
#include <bits/stdc++.h> 

#define pb push_back 
#define F first 
#define S second 
#define all(a) a.begin(),a.end() 
#define pii pair<int,int> 
#define ll long long
using namespace std ;
const int maxn = 1520  ;
int dp[maxn][maxn] , n ,  d; 
vector <int>G[maxn] ;
void dfs(int v){
  for(int i =0 ; i < G[v].size() ; i++){
    int u = G[v][i] ; 
    dfs(u) ; 
  }
  dp[v][0] = 1; 
  int sum[d+10] ;
  for(int i = 0 ; i <= d ; i++)sum[i] = 0 ; 
  for(int i =0 ; i <  G[v].size() ; i++){
    int u = G[v][i] ; 
    dp[v][0]+=dp[u][d-1] ; 
    for(int j = 0 ;  j <= d ; j++){
      sum[j+1] += dp[u][j] ; 
    }
  }
  for(int i =0 ; i <  G[v].size() ; i++){
    int u = G[v][i] ; 
    for(int j = (d+1) / 2 ; j <= d ; j++){
      dp[v][j] = sum[j] ;   
    }
    for(int j = 1 ; j < (d+1)/2 ; j++){
      dp[v][j] = max(sum[d-j] - dp[u][d-j-1] + dp[u][j-1] , dp[v][j]) ;
    }
  }
  for(int i= d-1 ; i >= 0 ;i--){
    dp[v][i] = max(dp[v][i] , dp[v][i+1]) ; 
  }
} 
  
signed main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin >> n >> d ;
  for(int i = 1; i < n ; i++){
    int x; 
    cin >> x ;
    G[x].pb(i) ; 
  }
  dfs(0) ; 
  int ans =0 ; 
  for(int i = 0 ; i <= d ; i++){
    ans = max(ans , dp[0][i]) ;
  }
  cout << ans ;
} 
/*


*/

Compilation message

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
catinatree.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i =0 ; i <  G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~
catinatree.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i =0 ; i <  G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 368 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 368 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 11 ms 9456 KB Output is correct
22 Correct 1 ms 2284 KB Output is correct
23 Correct 2 ms 2260 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 2 ms 4328 KB Output is correct
27 Correct 2 ms 4328 KB Output is correct
28 Correct 3 ms 6484 KB Output is correct
29 Correct 4 ms 6356 KB Output is correct
30 Correct 3 ms 6484 KB Output is correct
31 Correct 4 ms 6640 KB Output is correct
32 Correct 3 ms 6228 KB Output is correct
33 Correct 4 ms 6260 KB Output is correct
34 Correct 3 ms 5972 KB Output is correct
35 Correct 3 ms 5992 KB Output is correct
36 Correct 4 ms 6484 KB Output is correct
37 Correct 3 ms 6380 KB Output is correct
38 Correct 4 ms 6620 KB Output is correct
39 Correct 4 ms 6880 KB Output is correct
40 Correct 3 ms 6616 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 368 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 11 ms 9456 KB Output is correct
22 Correct 1 ms 2284 KB Output is correct
23 Correct 2 ms 2260 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 2 ms 4328 KB Output is correct
27 Correct 2 ms 4328 KB Output is correct
28 Correct 3 ms 6484 KB Output is correct
29 Correct 4 ms 6356 KB Output is correct
30 Correct 3 ms 6484 KB Output is correct
31 Correct 4 ms 6640 KB Output is correct
32 Correct 3 ms 6228 KB Output is correct
33 Correct 4 ms 6260 KB Output is correct
34 Correct 3 ms 5972 KB Output is correct
35 Correct 3 ms 5992 KB Output is correct
36 Correct 4 ms 6484 KB Output is correct
37 Correct 3 ms 6380 KB Output is correct
38 Correct 4 ms 6620 KB Output is correct
39 Correct 4 ms 6880 KB Output is correct
40 Correct 3 ms 6616 KB Output is correct
41 Runtime error 3 ms 724 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -