Submission #1081330

#TimeUsernameProblemLanguageResultExecution timeMemory
1081330oscar1fJobs (BOI24_jobs)C++17
11 / 100
199 ms63972 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int MAX_SOM=300*1000+5; 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]; void afficher(int pos) { 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) { while (!memo[petit].empty()) { memo[pos].push({-(-memo[petit].top().first+decal[petit]-decal[pos]),memo[petit].top().second}); memo[petit].pop(); } } void ajout(int pos,int valAjout) { decal[pos]-=valAjout; while (!memo[pos].empty() and decal[pos]-memo[pos].top().first<=0) { valAjout+=memo[pos].top().second; memo[pos].pop(); } memo[pos].push({decal[pos],valAjout}); } void retrait(int pos,int valSuppr) { //cout<<"!!!!!"<<pos<<" "<<valSuppr<<" "<<gainSur[pos]<<endl; decal[pos]+=valSuppr; int gain=-valSuppr,dernDec=0; while (!memo[pos].empty() and gain<=0) { dernDec=-memo[pos].top().first; gain+=memo[pos].top().second; memo[pos].pop(); } 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=i; 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]);*/ } int argFin=argDeb; //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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...