Submission #1236040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236040		inesfi	Magic Tree (CEOI19_magictree)	C++20	13 / 100	2121 ms	801916 KiB

magictree

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int TAILLEMAXI=100*1000+2,JOURSMAXI=1002;
vector<int> enfants[TAILLEMAXI];
int bonus_fruit[TAILLEMAXI];
int jour_fruit[TAILLEMAXI];
int memo[TAILLEMAXI][JOURSMAXI];
int cor[TAILLEMAXI];
int nbnoeuds,nbfruits,nbjoursmaxi;

void renum(){
    for (int i=1;i<=nbnoeuds;i++){
        if (jour_fruit[i]!=0){
            cor[jour_fruit[i]]=1;
        }
    }
    int compt=0;
    for (int i=1;i<=nbjoursmaxi;i++){
        if (cor[i]!=0){
            cor[i]=compt;
            compt++;
        }
    }
    for (int i=1;i<=nbnoeuds;i++){
        if (jour_fruit[i]!=0){
            jour_fruit[i]=cor[jour_fruit[i]];
        }
    }
}

int dp(int a,int jourmax){
    if (memo[a][jourmax]!=-1){
        return memo[a][jourmax];
    }
    if (enfants[a].size()==0){
        if (jour_fruit[a]<=jourmax){
            memo[a][jourmax]=bonus_fruit[a];
            return bonus_fruit[a];
        }
        memo[a][jourmax]=0;
        return 0;
    }
    int val1=0,val2=0;
    for (auto v:enfants[a]){
        val1+=dp(v,jourmax);
        val2+=dp(v,jour_fruit[a]);
    }
    int rep=0;
    if (jour_fruit[a]<=jourmax){
        //val2+=cb_par_jour[a][jour_fruit[a]];
        val2+=bonus_fruit[a];
        rep=val2;
    }
    rep=max(rep,val1);
    memo[a][jourmax]=rep;
    //cout<<a<<" "<<jourmax<<" "<<rep<<endl;
    return rep;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbnoeuds>>nbfruits>>nbjoursmaxi;
    for (int i=2;i<=nbnoeuds;i++){
        int val;
        cin>>val;
        enfants[val].push_back(i);
    }
    for (int i=0;i<nbfruits;i++){
        int s,j,w;
        cin>>s>>j>>w;
        bonus_fruit[s]=w;
        jour_fruit[s]=j;
    }
    renum();
    int rep=0;
    for (int i=1;i<=nbnoeuds;i++){
        for (int j=1;j<JOURSMAXI;j++){
            memo[i][j]=-1;
        }
    }
    for (auto i:enfants[1]){
        rep+=dp(i,JOURSMAXI-1);
    }
    cout<<rep<<endl;
    /*for (int i=1;i<=nbnoeuds;i++){
        for (int j=1;j<=nbjoursmaxi;j++){
            cout<<cb_par_jour[i][j]<<" ";
        }
        cout<<endl;
    }*/
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 13 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17