Submission #557823

#	Time	Username	Problem	Language	Result	Execution time	Memory
557823		fatemetmhr	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	42 ms	18036 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second

const int maxn5 = 2e3 + 10;

int d;
int dp[maxn5][maxn5];
int tmp[maxn5], sz[maxn5];
vector <int> adj[maxn5];

inline void dfs(int v){
    sz[v] = 1;
    for(auto u : adj[v]){
        dfs(u);
        memset(tmp, 0, sizeof tmp);
        for(int i = 0; i <= sz[u]; i++) for(int j = 0; j <= sz[v]; j++) if(i + 1 + j >= d){
            tmp[min(i + 1, j)] = max(tmp[min(i + 1, j)], dp[v][j] + dp[u][i]);
        }
        for(int i = 0; i <= sz[u]; i++)
            tmp[i + 1] = max(tmp[i + 1], dp[u][i]);
        sz[v] += sz[u];
        for(int i = 0; i <= sz[v]; i++){
            dp[v][i] = max(dp[v][i], tmp[i]);
            //cout << "se of " << v << ' '<< u << ' ' << i << ' ' << dp[v][i] << ' ' << tmp[i] << endl;    
        }
    }
    dp[v][0] = max(dp[v][0], dp[v][d] + 1);
    //for(int i = 0; i <= d; i++)
        //cout << v << ' '<< i << ' '<< dp[v][i] << endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n >> d;
    for(int i = 1; i < n; i++){
        int a; cin >> a;
        adj[a].pb(i);
    }
    dfs(0);
    int ans = *max_element(dp[0], dp[0] + n + 5);
    cout << ans << endl;
}

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