Submission #565456

#	Time	Username	Problem	Language	Result	Execution time	Memory
565456		Jesus	Ideal city (IOI12_city)	C++14	100 / 100	54 ms	10532 KiB

city

#include <bits/stdc++.h>

using namespace std;


int lim;

queue<int> camino;

struct nodo{
    int familia=0;
    int pa=0;
    int pb=0;
    long long int cantidad=0;
    int lvl=0;
    vector<int> conexiones;
};

nodo arbol[100001];


pair<int,int> valores[100001];

void ciclo(int pos){
    while(camino.size()>0){
        int aux=camino.front();
        if(arbol[pos].familia>arbol[aux].familia+1) camino.pop();
        else if(arbol[pos].familia>arbol[aux].familia){
            if(arbol[aux].pa>arbol[pos].pb) break;
            if((arbol[aux].pa>=arbol[pos].pa)||(arbol[aux].pa<arbol[pos].pa&&arbol[aux].pb>=arbol[pos].pa)){
                arbol[pos].conexiones.push_back(aux);
                arbol[pos].lvl++;
                arbol[aux].conexiones.push_back(pos);
                arbol[aux].lvl++;
            }
            if(arbol[aux].pb<=arbol[pos].pb) camino.pop();
            else break;
        }
        else break;
    }
}

void generar_arbol(){

    int pos=0;
    arbol[0].familia=valores[0].first;
    arbol[0].pa=valores[0].second; arbol[0].pb=valores[0].second;
    arbol[0].cantidad=1;
    pair<int,int> anterior=valores[0];

    swap(valores[0].first,valores[0].second);

    for(int i=1;i<lim;i++){
        if(anterior.first==valores[i].first&&valores[i].second-anterior.second==1){
            arbol[pos].cantidad++;
            arbol[pos].pb=valores[i].second;
        }

        else{
            ciclo(pos);
            camino.push(pos);
            pos++;
            arbol[pos].cantidad=1;
            arbol[pos].familia=valores[i].first; arbol[pos].pa=valores[i].second; arbol[pos].pb=valores[i].second;
        }

        anterior=valores[i];

        swap(valores[i].first,valores[i].second);
    }

    ciclo(pos);

    while(camino.size()>0){
        camino.pop();
    }

}


void encontrar_extremos(int padre=-1, int pos=0){
    if(arbol[pos].lvl==1) camino.push(pos);
    for(int nod: arbol[pos].conexiones){
        if(nod!=padre) encontrar_extremos(pos,nod);
    }
}

long long int pasos(){

    long long int sum=0;

    while(camino.size()>0){
        nodo reiniciar;
        int aux=camino.front();
        sum+=(arbol[aux].cantidad*(lim-arbol[aux].cantidad))%1000000000;
        sum%=1000000000;
        arbol[aux].lvl--;
        for(int nod:arbol[aux].conexiones){
            if(arbol[nod].lvl>=1){
                arbol[nod].lvl--;
                arbol[nod].cantidad+=arbol[aux].cantidad;
                if(arbol[nod].lvl==1) camino.push(nod);
                else if(arbol[nod].lvl==0) arbol[nod]=reiniciar;
            }
        }
        arbol[aux]=reiniciar;

        camino.pop();
    }

    return sum;
}



int DistanceSum(int N, int *X, int *Y) {
    long long int total=0;

    for(int i=0;i<N;i++){
        valores[i]={X[i],Y[i]};
    }
    sort(valores,valores+N);

    lim=N;

    generar_arbol();
    encontrar_extremos();
    total=pasos();


    sort(valores,valores+N);

    generar_arbol();
    encontrar_extremos();
    total+=pasos();

    total%=1000000000;

    return total;

}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45