Submission #1106304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106304		Arturgo	Nile (IOI24_nile)	C++17	100 / 100	85 ms	21164 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
struct relique{
    int p,cout1,pere;
 
    bool operator< (relique other){
        return p<other.p;
    }
};
 
struct quest{
    int q,numquest;
 
    bool operator< (quest other){
        return q<other.q;
    }
};
 
struct compo{
    int pere,premier,dernier,minpair,minimpair,minponts,prix;
};
 
struct dist{
    int d,premier;
 
    bool operator< (dist other){
        return d<other.d;
    }
};
 
const int INFINI=1000ll*1000*1000*1000*1000*1000ll+2,QUESTMAXI=100*1000+2;
vector<relique> reliques;
vector<quest> questions;
vector<compo> composantes;
int nbreliques,ajout;
vector<dist> aretes;
vector<dist> ponts2;
int reponse[QUESTMAXI];
vector<int> r;
 
int trouver(int numc){
    if (composantes[numc].pere!=numc){
        return composantes[numc].pere=trouver(composantes[numc].pere);
    }
    return numc;
}
 
void unir(int compo1,int compo2){
    compo1=trouver(compo1);
    compo2=trouver(compo2);
    ajout-=composantes[compo1].prix+composantes[compo2].prix;
    
    composantes[compo2].pere=compo1;
    compo nouv;
    nouv.pere=compo1;
    nouv.premier=min(composantes[compo1].premier,composantes[compo2].premier);
    nouv.dernier=max(composantes[compo1].dernier,composantes[compo2].dernier);
    nouv.minpair=min(composantes[compo1].minpair,composantes[compo2].minpair);
    nouv.minimpair=min(composantes[compo1].minimpair,composantes[compo2].minimpair);
    nouv.minponts=min(composantes[compo1].minponts,composantes[compo2].minponts);
    if ((nouv.dernier-nouv.premier)%2==1){
        nouv.prix=0;
    }
    else {
        if (nouv.premier%2==0){
            nouv.prix=min(nouv.minpair,nouv.minponts);
        }
        else {
            nouv.prix=min(nouv.minimpair,nouv.minponts);
        }
    }
    composantes[compo1]=nouv;
    ajout+=nouv.prix;
}
#undef int
 
vector<long long> calculate_costs(vector<int> poids, vector<int> seul, vector<int> deux, vector<int> requetes) {
    #define int long long
    nbreliques=(int)poids.size();
    for (int irelique=0;irelique<nbreliques;irelique++){
        relique rel;
        ajout+=deux[irelique];
        rel.p=poids[irelique];
        rel.cout1=seul[irelique]-deux[irelique];
        rel.pere=0;
        reliques.push_back(rel);
    }
    sort(reliques.begin(),reliques.end());
    for (int irelique=0;irelique<nbreliques;irelique++){
        reliques[irelique].pere=irelique;
    }
    for (int iquest=0;iquest<(int)requetes.size();iquest++){
        quest qu;
        qu.q=requetes[iquest];
        qu.numquest=iquest;
        questions.push_back(qu);
    }
    sort(questions.begin(),questions.end());
    for (int irelique=0;irelique<nbreliques;irelique++){
        compo c;
        if (irelique%2==0){
            c={irelique,irelique,irelique,reliques[irelique].cout1,INFINI,INFINI,reliques[irelique].cout1};
        }
        else {
            c={irelique,irelique,irelique,INFINI,reliques[irelique].cout1,INFINI,reliques[irelique].cout1};
        }
        ajout+=reliques[irelique].cout1;
        composantes.push_back(c);
    }
    for (int irelique=0;irelique<nbreliques-1;irelique++){
        dist ar;
        ar={reliques[irelique+1].p-reliques[irelique].p,irelique};
        aretes.push_back(ar);
    }
    sort(aretes.begin(),aretes.end());
    for (int irelique=0;irelique<nbreliques-2;irelique++){
        dist ar;
        ar={reliques[irelique+2].p-reliques[irelique].p,irelique};
        ponts2.push_back(ar);
    }
    sort(ponts2.begin(),ponts2.end());
    int arec=0,pontec=0;
    for (auto qec:questions){
        while (arec<nbreliques-1 and aretes[arec].d<=qec.q){
            unir(aretes[arec].premier,aretes[arec].premier+1);
            arec++;
        }
        while (pontec<nbreliques-2 and ponts2[pontec].d<=qec.q){
            composantes[trouver(ponts2[pontec].premier+1)].minponts=min(composantes[trouver(ponts2[pontec].premier+1)].minponts,
            reliques[ponts2[pontec].premier+1].cout1);
            ajout-=composantes[trouver(ponts2[pontec].premier+1)].prix;
            composantes[trouver(ponts2[pontec].premier+1)].prix=min(composantes[trouver(ponts2[pontec].premier+1)].prix,
            composantes[trouver(ponts2[pontec].premier+1)].minponts);
            ajout+=composantes[trouver(ponts2[pontec].premier+1)].prix;
            pontec++;
        }
        reponse[qec.numquest]=ajout;
    }
    for (int irep=0;irep<(int)requetes.size();irep++){
        r.push_back(reponse[irep]);
    }
    return r;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18