oj.uz

Submission #565456

# Submission time Handle Problem Language Result Execution time Memory
565456 2022-05-20T22:32:04 Z Jesus Ideal city (IOI12_city) C++14
100 / 100
 54 ms 10532 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 5 ms 5792 KB Output is correct
3 Correct 4 ms 5716 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct
10 Correct 4 ms 5716 KB Output is correct
11 Correct 4 ms 5716 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5808 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5804 KB Output is correct
5 Correct 4 ms 5800 KB Output is correct
6 Correct 7 ms 5844 KB Output is correct
7 Correct 5 ms 5844 KB Output is correct
8 Correct 5 ms 5800 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 4 ms 5844 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6228 KB Output is correct
2 Correct 10 ms 6228 KB Output is correct
3 Correct 21 ms 6944 KB Output is correct
4 Correct 21 ms 6956 KB Output is correct
5 Correct 51 ms 8104 KB Output is correct
6 Correct 37 ms 8124 KB Output is correct
7 Correct 39 ms 8360 KB Output is correct
8 Correct 38 ms 8152 KB Output is correct
9 Correct 40 ms 8352 KB Output is correct
10 Correct 42 ms 10532 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6484 KB Output is correct
2 Correct 12 ms 6484 KB Output is correct
3 Correct 26 ms 7704 KB Output is correct
4 Correct 24 ms 7508 KB Output is correct
5 Correct 52 ms 9524 KB Output is correct
6 Correct 45 ms 8772 KB Output is correct
7 Correct 54 ms 9676 KB Output is correct
8 Correct 54 ms 8820 KB Output is correct
9 Correct 44 ms 8564 KB Output is correct
10 Correct 44 ms 8524 KB Output is correct