Submission #1081320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081320		oscar1f	Jobs (BOI24_jobs)	C++17	0 / 100	188 ms	61372 KiB

Main

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

#define int long long

const int MAX_SOM=300*1000+5,INFINI=(int)2*1000*1000*1000*1000*1000*1000;
int nbSom,argDeb;
int val[MAX_SOM],pere[MAX_SOM];
vector<int> listeFils[MAX_SOM];
int posEcri[MAX_SOM];
priority_queue<pair<int,int>> memo[MAX_SOM];
int decal[MAX_SOM],gainSur[MAX_SOM];

void afficher(int pos) {
    cout<<"!"<<gainSur[pos]<<" "<<decal[pos]<<endl;
    auto temp=memo[pos];
    cout<<memo[pos].size()<<endl;
    while (!temp.empty()) {
        cout<<-temp.top().first+decal[pos]<<" "<<temp.top().second<<endl;
        temp.pop();
    }
    cout<<endl;
}

void insere(int pos,int petit) {
    gainSur[pos]+=gainSur[petit];
    while (!memo[petit].empty()) {
        memo[pos].push({-(-memo[petit].top().first+decal[petit]-decal[pos]),memo[petit].top().second});
        memo[petit].pop();
    }
    while (!memo[pos].empty() and decal[pos]-memo[pos].top().first<=0) {
        gainSur[pos]+=memo[pos].top().second;
        memo[pos].pop();
    }
}

void ajout(int pos,int valAjout) {
    gainSur[pos]+=valAjout;
    decal[pos]-=valAjout;
    while (!memo[pos].empty() and decal[pos]-memo[pos].top().first<=0) {
        gainSur[pos]+=memo[pos].top().second;
        memo[pos].pop();
    }
}

void retrait(int pos,int valSuppr) {
    //cout<<"!!!!!"<<pos<<" "<<valSuppr<<" "<<gainSur[pos]<<endl;
    decal[pos]+=valSuppr;
    int gain=gainSur[pos]-valSuppr,dernDec=0;
    gainSur[pos]=0;
    while (!memo[pos].empty() and gain<=0) {
        dernDec=-memo[pos].top().first;
        gain+=memo[pos].top().second;
    }
    if (gain>0) {
        memo[pos].push({-dernDec,gain});
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>argDeb;
    for (int i=1;i<=nbSom;i++) {
        cin>>val[i]>>pere[i];
        listeFils[pere[i]].push_back(i);
    }
    int maxFils,valMax;
    for (int i=nbSom;i>=0;i--) {
        valMax=-1;
        maxFils=-1;
        for (int j:listeFils[i]) {
            if (!memo[posEcri[j]].empty() and (int)memo[posEcri[j]].size()>valMax) {
                valMax=memo[posEcri[j]].size();
                maxFils=j;
            } 
        }
        if (valMax==-1) {
            posEcri[i]=i;
        }
        else {
            posEcri[i]=posEcri[maxFils];
        }
        for (int j:listeFils[i]) {
            //cout<<"?"<<i<<" "<<j<<endl; 
            if (j!=maxFils) {
                insere(posEcri[i],posEcri[j]);
            }
        }
        if (val[i]>0) {
            ajout(posEcri[i],val[i]);
        }
        else if (val[i]<0) {
            retrait(posEcri[i],-val[i]);
        }
        /*cout<<posEcri[i]<<endl;
        afficher(posEcri[i]);
        for (int j=0;j<=nbSom;j++) {
            cout<<gainSur[j]<<" ";
        }
        cout<<endl;*/
    }
    int argFin=argDeb;
    argFin+=gainSur[posEcri[0]];
    //cout<<argFin<<" "<<-memo[posEcri[0]].top().first+decal[posEcri[0]]<<endl;

    while (!memo[posEcri[0]].empty() and argFin>=-memo[posEcri[0]].top().first+decal[posEcri[0]]) {
        argFin+=memo[posEcri[0]].top().second;
        memo[posEcri[0]].pop();
    }
    cout<<argFin-argDeb<<endl;
    return 0;
}
 

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31