Submission #1126866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126866		BlancaHM	Saveit (IOI10_saveit)	C++17	100 / 100	72 ms	5808 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <queue>
#include <vector>

using namespace std;


// Calcula la longitud del camino mas corto desde la fuente al resto de ciudades.
vector<int> caminoMasCortoATodasLasCiudades(int fuente, vector<vector<int>> & listaAdyacencia) {
    int numCiudades = (int) listaAdyacencia.size();
    vector<int> distancias(numCiudades, numCiudades + 1);
    distancias[fuente] = 0;
    queue<int> colaBfs;
    colaBfs.push(fuente);
    while (!colaBfs.empty()) {
        int ciudad = colaBfs.front();
        colaBfs.pop();
        for (int & vecina: listaAdyacencia[ciudad]) {
            if (distancias[vecina] > distancias[ciudad] + 1) {
                distancias[vecina] = distancias[ciudad] + 1;
                colaBfs.push(vecina);
            }
        }
    }
    return distancias;
}


// Calcula la distancia entre todos los centros de actividades y todas las ciudades.
vector<vector<int>> todasLasDistancias(
    vector<vector<int>> & listaAdyacencia, int numCentros
) {
    vector<vector<int>> distancias(numCentros);
    for (int i = 0; i < numCentros; i++) {
        distancias[i] = caminoMasCortoATodasLasCiudades(i, listaAdyacencia);
    }
    return distancias;
}


// Encuentra el arbol BFS del grafo y saber el padre de cada ciudad.
vector<int> definePadres(vector<vector<int>> & listaAdyacencia) {
    vector<int> padre(listaAdyacencia.size(), -1);
    queue<int> colaBfs;
    colaBfs.push(0);
    padre[0] = -2;
    while (!colaBfs.empty()) {
        int ciudad = colaBfs.front();
        colaBfs.pop();

        // Definimos el padre como la primera conexion que vemos de la ciudad.
        for (int & vecina: listaAdyacencia[ciudad]) {
            if (padre[vecina] == -1) {
                padre[vecina] = ciudad;
                colaBfs.push(vecina);
            }
        }
    }
    padre[0] = -1;
    return padre;
}


// Codifica un numero decimal en numBits columnas binarias.
void codificaEnBits(int numero, int numBits) {
    vector<int> bits(numBits);
    for (int idx = numBits - 1; idx >= 0; idx--) {
        bits[numBits - idx - 1] = numero / (1 << idx);
        numero %= (1 << idx);
    }
    for (int i = 0; i < numBits; i++) {
        encode_bit((bool) bits[i]);
    }
}

void encode(int numCiudades, int numCentros, int numConexiones, int * v1, int * v2) {
    vector<vector<int>> listaAdyacencia(numCiudades);
    for (int i = 0; i < numConexiones; i++) {
        listaAdyacencia[v1[i]].push_back(v2[i]);
        listaAdyacencia[v2[i]].push_back(v1[i]);
    }

    // Primero, definimos y codificamos los padres de todas las ciudades.
    vector<int> padre = definePadres(listaAdyacencia);
    for (int i = 1; i < numCiudades; i++) {
        codificaEnBits(padre[i], 10);
    }

    // Encontramos todas las distancias entre centros y ciudades y las codificamos.
    vector<vector<int>> distancias = todasLasDistancias(listaAdyacencia, numCentros);
    int ciudad, diferenciaDistancias, diferenciasAgregadas;
    for (int hub_idx = 0; hub_idx < numCentros; hub_idx++) {
        ciudad = 1;

        // Codificamos las distancias en grupos de 3 hasta que ya no haya grupos.
        while (ciudad + 2 < numCiudades) {
            // Al tener 3 diferencias, todas ellas en {0, 1, 2}, podemos codificarlas en 5 bits,
            // ya que 2^5 >= 3^3.
            diferenciasAgregadas = 0;
            for (int diff = 0; diff < 3; diff++) {
                diferenciaDistancias = (
                    distancias[hub_idx][ciudad + diff] - distancias[hub_idx][padre[ciudad + diff]] + 1
                );
                diferenciasAgregadas = 3 * diferenciasAgregadas + diferenciaDistancias;
            }
            codificaEnBits(diferenciasAgregadas, 5);
            ciudad += 3;
        }

        // Codificamos el resto de forma aislada.
        while (ciudad < numCiudades) {
            diferenciaDistancias = distancias[hub_idx][ciudad] - distancias[hub_idx][padre[ciudad]] + 1;
            // Como la diferencia es 0, 1 o 2, nos bastan 2 bits para codificarla.
            codificaEnBits(diferenciaDistancias, 2);
            ciudad++;
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <queue>
#include <vector>

using namespace std;


// Descodifica un numero decimal recibido en numBits columnas binarias.
int decode_in_bits(int numBits) {
    vector <int> bits(numBits);
    for (int i = 0; i < numBits; i++) {
        bits[i] = (int) decode_bit();
    }
    int numero = 0;
    for (int idx = numBits - 1; idx >= 0; idx--) {
        numero += bits[numBits - idx - 1] * (1 << idx);
    }
    return numero;
}


// Recupera las distancias desde la fuente al resto de ciudades.
vector<int> recuperarDistancias(
    int fuente,
    vector<vector<int>> & listaAdyacenciaArbol,
    vector<int> & diferenciasDistancia,
    vector<int> & padre
) {
    // Hacemos una BFS desde la fuente, calculando la distancia total con las diferencias.
    vector <int> distancias(listaAdyacenciaArbol.size(), -1);
    distancias[fuente] = 0;
    queue <int> colaBfs;
    colaBfs.push(fuente);
    while (!colaBfs.empty()) {
        int ciudad = colaBfs.front();
        colaBfs.pop();

        for (int & vecina: listaAdyacenciaArbol[ciudad]) {
            if (distancias[vecina] != -1) {
                continue;
            }
            if (padre[vecina] == ciudad) {
                distancias[vecina] = distancias[ciudad] + diferenciasDistancia[vecina];
            } else {
                // Sabemos que padre[ciudad] == vecina en este caso.
                distancias[vecina] = distancias[ciudad] - diferenciasDistancia[ciudad];
            }
            colaBfs.push(vecina);
        }
    }

    return distancias;
}


void decode(int numCiudades, int numCentros) {
    // Primero, reconstruimos el arbol de expansion.
    vector<vector<int>> listaAdyacenciaArbol(numCiudades);
    vector<int> padre(numCiudades, -1);
    for (int i = 1; i < numCiudades; i++) {
        int p = decode_in_bits(10);
        listaAdyacenciaArbol[p].push_back(i);
        listaAdyacenciaArbol[i].push_back(p);
        padre[i] = p;
    }

    // Recuperamos las distancias gracias a las diferencias en el arbol.
    vector<vector<int>> distancias(numCentros, vector<int>(numCiudades));
    vector<int> diferenciasDistancia(numCiudades);
    for (int centro = 0; centro < numCentros; centro++) {
        int ciudad = 1, distanciaAgregada;
        while (ciudad + 2 < numCiudades) {
            distanciaAgregada = decode_in_bits(5);
            for (int diff = 2; diff >= 0; diff--) {
                diferenciasDistancia[ciudad + diff] = (distanciaAgregada % 3) - 1;
                distanciaAgregada /= 3;
            }
            ciudad += 3;
        }
        while (ciudad < numCiudades) {
            diferenciasDistancia[ciudad] = decode_in_bits(2) - 1;
            ciudad++;
        }

        distancias[centro] = recuperarDistancias(centro, listaAdyacenciaArbol, diferenciasDistancia, padre);
    }

    // Enviamos las distancias para que el juez las corrija.
    for (int centro = 0; centro < numCentros; centro++) {
        for (int ciudad = 0; ciudad < numCiudades; ciudad++) {
            hops(centro, ciudad, distancias[centro][ciudad]);
        }
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25