Submission #960532

#	Time	Username	Problem	Language	Result	Execution time	Memory
960532		inesfi	Fountain (eJOI20_fountain)	C++17	100 / 100	222 ms	28976 KiB

fountain

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

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

const int TAILLEMAXI=100*1000+2,INFINI=1000*1000*1000+2,LOGMAXI=19;
int nbcercles,nbquestions,val,noeud,ajouter,contenance,numcercle;
int peres[TAILLEMAXI][LOGMAXI],cumu[TAILLEMAXI];
vector<int> enfant[TAILLEMAXI];
deque<pair<int,int>> encours;
set<pair<int,int>> atrouver;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbcercles>>nbquestions;
    cumu[0]=INFINI;
    for (int icercle=1;icercle<=nbcercles;icercle++){
        cin>>val>>contenance;
        atrouver.insert(make_pair(val,icercle));
        while ((*(atrouver.begin())).first<val){
            enfant[icercle].push_back((*(atrouver.begin())).second);
            peres[(*(atrouver.begin())).second][0]=icercle;
            atrouver.erase(atrouver.begin());
        }
        cumu[icercle]=contenance;
    }
    while ((int)atrouver.size()!=0){
        peres[(*(atrouver.begin())).second][0]=0;
        enfant[0].push_back((*(atrouver.begin())).second);
        atrouver.erase(atrouver.begin());
    }
    encours.push_back(make_pair(0,0));
    while ((int)encours.size()!=0){
        noeud=encours.front().first;
        ajouter=encours.front().second;
        encours.pop_front();
        cumu[noeud]+=ajouter;
        for (int ienfant=0;ienfant<enfant[noeud].size();ienfant++){
            encours.push_back(make_pair(enfant[noeud][ienfant],cumu[noeud]));
        }
    }
    /*for (int isommet=1;isommet<=nbcercles;isommet++){
        cout<<cumu[isommet]<<" "<<peres[isommet]<<endl;
    }*/
    for (int ilog=1;ilog<LOGMAXI;ilog++){
        for (int isommet=1;isommet<=nbcercles;isommet++){
            peres[isommet][ilog]=peres[peres[isommet][ilog-1]][ilog-1];
        }
    }
    for (int iquestion=0;iquestion<nbquestions;iquestion++){
        cin>>numcercle>>contenance;
        for (int ilog=LOGMAXI-1;ilog>=0;ilog--){
            if (cumu[numcercle]-cumu[peres[numcercle][ilog]]<contenance){
                contenance-=cumu[numcercle]-cumu[peres[numcercle][ilog]];
                numcercle=peres[numcercle][ilog];
            }
        }
        cout<<numcercle<<endl;
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:41:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int ienfant=0;ienfant<enfant[noeud].size();ienfant++){
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40