Submission #1111007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111007		dangmotm07	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	34 ms	27472 KiB

catinatree

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
vector<vector<int> > prv, sum_f, suf, f;
int n, D;
int tmp[maxn];
vector<int> adj[maxn];
int f1[maxn], f2[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 - 1];
        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)]);

        }
    }
   // if(u == 1) cout<<cnt;
    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]);
}

void sub2() {
     dfs(1, 0);
    int ds = 0;
    for(int j=0;j<=D;j++) ds = max(ds, f[1][j]);
    cout<<ds;
}
void cal(int u, int dad) {
    for(int v:adj[u]) if(v != dad) {
        cal(v, u);
        if(f1[u] < f1[v] + 1) {
            f2[u] = f1[u];
            f1[u] = f1[v] + 1;
        }
        else if(f2[u] < f1[v] + 1) {
            f2[u] = f1[v] + 1;
        }
    }
}
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);
    }
    cal(1, 0);
    int cur = 0;
    for(int i=1;i<=n;i++) {
        cur = max(cur, f1[i] + f2[i]);
    }
    D = min(D, cur + 1);
    prv.resize(n + 5, vector<int> (D + 5, 0));
    sum_f.resize(n + 5, vector<int> (D + 5, 0));
    f.resize(n + 5, vector<int> (D + 5, 0));
    suf.resize(n + 5, vector<int> (D + 5, 0));
    sub2();
}

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