Submission #783361

#	Time	Username	Problem	Language	Result	Execution time	Memory
783361		oscar1f	Two Currencies (JOI23_currencies)	C++17	100 / 100	880 ms	49356 KiB

currencies

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

#define int long long

const int MAX_SOM=100*1000+5,MAX_LOG=18,MAX_REQ=100*1000+5,DECA=(1<<17);
int nbSom,nbCheck,nbReq,idAre,coutArg,idSom,nbRest;
vector<int> adja[MAX_SOM];
int are[MAX_SOM][2];
int prof[MAX_SOM];
int pere[MAX_SOM][MAX_LOG];
int req[MAX_REQ][6];
int num[MAX_SOM];
int sousArbre[MAX_SOM][2];
vector<pair<int,int>> checkTri;
vector<int> reqDeb;
int cumu[2*DECA][2];

void DFS(int pos,int anci,int etage) {
    if (prof[pos]==0) {
        //cout<<pos<<" "<<anci<<" "<<etage<<endl;
        pere[pos][0]=anci;
        prof[pos]=etage;
        idSom++;
        num[pos]=idSom;
        sousArbre[pos][0]=idSom;
        for (int vois:adja[pos]) {
            DFS(vois,pos,etage+1);
        }
        sousArbre[pos][1]=idSom;
    }
}

int lca(int som1,int som2) {
    if (prof[som1]>prof[som2]) {
        swap(som1,som2);
    }
    for (int i=MAX_LOG-1;i>=0;i--) {
        if (prof[pere[som2][i]]>=prof[som1]) {
            som2=pere[som2][i];
        }
    } 
    if (som1==som2) {
        return som1;
    }
    for (int i=MAX_LOG-1;i>=0;i--) {
        if (pere[som1][i]!=pere[som2][i]) {
            som1=pere[som1][i];
            som2=pere[som2][i];
        }
    }
    return pere[som1][0];
}

void ajout(int deb,int fin,int val,int idTab) {
    if (deb==fin) {
        cumu[deb][idTab]+=val;
    }
    else if (deb%2==1) {
        cumu[deb][idTab]+=val;
        ajout(deb+1,fin,val,idTab);
    }
    else if (fin%2==0) {
        cumu[fin][idTab]+=val;
        ajout(deb,fin-1,val,idTab);
    }
    else {
        ajout(deb/2,fin/2,val,idTab);
    }
}

int calcVal(int pos,int idTab) {
    int somme=0;
    while (pos!=0) {
        somme+=cumu[pos][idTab];
        pos/=2;
    }
    return somme;
}

void addAre(int i,int coeff) {
    //cout<<i<<" : "<<sousArbre[are[checkTri[i].second][1]][0]<<" "<<sousArbre[are[checkTri[i].second][1]][1]<<endl;
    ajout(DECA+sousArbre[are[checkTri[i].second][1]][0],DECA+sousArbre[are[checkTri[i].second][1]][1],checkTri[i].first*coeff,0);
    ajout(DECA+sousArbre[are[checkTri[i].second][1]][0],DECA+sousArbre[are[checkTri[i].second][1]][1],coeff,1);
}

int calcDist(int r,int idTab) {
    /*cout<<endl;
    cout<<r<<" "<<idTab<<endl;
    cout<<num[req[r][0]]<<" = "<<calcVal(DECA+num[req[r][0]],idTab)<<endl;
    cout<<num[req[r][1]]<<" = "<<calcVal(DECA+num[req[r][1]],idTab)<<endl;
    cout<<num[req[r][5]]<<" = "<<calcVal(DECA+num[req[r][5]],idTab)<<endl;*/
    return calcVal(DECA+num[req[r][0]],idTab)+calcVal(DECA+num[req[r][1]],idTab)-2*calcVal(DECA+num[req[r][5]],idTab);
}

void calc(int debInter,int finInter,int posCour,vector<int> reqCour) {
    if (reqCour.empty()) {
        return;
    }
    int midInter=(debInter+finInter+1)/2;
    if (finInter==-1) {
        midInter=-1;
    }

    /*cout<<debInter<<" "<<finInter<<" "<<posCour<<" "<<midInter<<" : ";
    for (int r:reqCour) {
        cout<<r<<" ";
    }
    cout<<endl;*/

    if (posCour<midInter) {
        for (int i=posCour+1;i<=midInter;i++) {
            addAre(i,1);
        }
    }
    else {
        for (int i=posCour;i>midInter;i--) {
            addAre(i,-1);
        }
    }

    /*for (int i=1;i<2*DECA;i++) {
        cout<<cumu[i][0]<<" "<<cumu[i][1]<<"      ";
    }
    cout<<endl;*/

    if (debInter==finInter) {
        for (int r:reqCour) {
            //cout<<r<<" "<<calcDist(r,0)<<" "<<calcDist(r,1)<<endl;
            req[r][4]=calcDist(r,1);
        }
    }
    else {
        vector<int> reqSous,reqSur;
        for (int r:reqCour) {
            //cout<<r<<" : "<<calcDist(r,0)<<endl;
            if (calcDist(r,0)>req[r][3]) {
                reqSous.push_back(r);
            } 
            else {
                reqSur.push_back(r);
            }
        }
        calc(debInter,midInter-1,midInter,reqSous);
        calc(midInter,finInter,midInter,reqSur);
    }

    if (posCour<midInter) {
        for (int i=posCour+1;i<=midInter;i++) {
            addAre(i,-1);
        }
    }
    else {
        for (int i=posCour;i>midInter;i--) {
            addAre(i,1);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>nbCheck>>nbReq;
    for (int i=1;i<nbSom;i++) {
        cin>>are[i][0]>>are[i][1];
        adja[are[i][0]].push_back(are[i][1]);
        adja[are[i][1]].push_back(are[i][0]);
    }
    DFS(1,0,1);
    /*for (int i=1;i<=nbSom;i++) {
        cout<<i<<" : "<<num[i]<<" "<<sousArbre[i][0]<<" "<<sousArbre[i][1]<<" "<<pere[i][0]<<" "<<prof[i]<<endl;
    }*/
    for (int j=1;j<MAX_LOG;j++) {
        for (int i=0;i<=nbSom;i++) {
            pere[i][j]=pere[pere[i][j-1]][j-1];
        }
    }
    for (int i=1;i<nbSom;i++) {
        if (prof[are[i][0]]>prof[are[i][1]]) {
            swap(are[i][0],are[i][1]);
        }
    }
    for (int i=0;i<nbCheck;i++) {
        cin>>idAre>>coutArg;
        checkTri.push_back({coutArg,idAre});
    }
    sort(checkTri.begin(),checkTri.end());
    for (int i=0;i<nbReq;i++) {
        cin>>req[i][0]>>req[i][1]>>req[i][2]>>req[i][3];
        reqDeb.push_back(i);
        req[i][5]=lca(req[i][0],req[i][1]);
    }
    calc(-1,nbCheck-1,-1,reqDeb);

    for (int i=0;i<nbCheck;i++) {
        addAre(i,1);
    }
    for (int i=0;i<nbReq;i++) {
        nbRest=calcDist(i,1)-req[i][4];
        //cout<<i<<" : "<<req[i][4]<<" "<<calcDist(i,1)<<" ";
        cout<<max(req[i][2]-nbRest,(int)-1)<<"\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32