Submission #716371

#	Time	Username	Problem	Language	Result	Execution time	Memory
716371		manizare	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	11 ms	9456 KiB

catinatree

#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 (stderr)

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 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49