Submission #1110997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110997		dangmotm07	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	2 ms	6480 KiB

catinatree

#include<bits/stdc++.h>
#define maxn 1505
using namespace std;
int n, D, prv[maxn][maxn], sum_f[maxn][maxn], suf[maxn][maxn], f[maxn][maxn];
int tmp[maxn];
vector<int> adj[maxn];

void dfs(int u, int dad) {
    for(int v:adj[u]) if(v != dad) dfs(v, u);
    f[u][0] = 1;
    int cnt = 0;
    for(int v:adj[u]) if(v != dad) {
        f[u][0] += sum_f[v][D];
        tmp[++cnt] = v;
    }
    for(int i=1;i<=cnt+1;i++)
        for(int j=1;j<=D;j++) prv[i][j] = 0, suf[i][j] = 0;

    for(int i=1;i<=cnt;i++) {
        for(int j=0;j<=D;j++) prv[i][j] = prv[i-1][j] + sum_f[tmp[i]][j];
    }
    for(int i=cnt;i>=1;i--) {
        for(int j=1;j<=D;j++) suf[i][j] = suf[i+1][j] + sum_f[tmp[i]][j];
    }
    for(int i=1;i<=D;i++) {
        for(int j=1;j<=cnt;j++) {
            f[u][i] = max(f[u][i], f[tmp[j]][i - 1] + prv[j-1][max(max(i, D - i) - 1, 0)] + suf[j + 1][max(max(i, D - i) - 1, 0)]);
        }
    }
    sum_f[u][D] = f[u][D];
    for(int i=D-1;i>=0;i--) sum_f[u][i] = max(sum_f[u][i + 1], f[u][i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>D;
    for(int i=1;i<n;i++) {
        int x;
        cin>>x;
        ++x;
        adj[x].push_back(i + 1);
        adj[i + 1].push_back(x);
    }
    dfs(1, 0);
    int ds = 0;
    for(int j=0;j<=D;j++) ds = max(ds, f[1][j]);

    cout<<ds;
}

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