Submission #1126860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126860		BlancaHM	Saveit (IOI10_saveit)	C++17	100 / 100	69 ms	5952 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;


int decode_in_bits(int num_bits) {
   // Decode a number received in num_bits bits to decimal.
  vector<int> bits(num_bits);
  for (int i = 0; i < num_bits; i++) {
    bits[i] = (int) decode_bit();
  }
  int number = 0;
  for (int idx = num_bits - 1; idx >= 0; idx--) {
    number += bits[num_bits - idx - 1] * (1 << idx);
  }
  return number;
}


vector<int> find_distances(
    int source,
    vector<vector<int>> & tree_adjacency,
    vector<int> & deltas,
    vector<int> & parent
) {
   vector<int> distance(tree_adjacency.size(), -1);
   distance[source] = 0;

   queue<int> bfs_queue;
   bfs_queue.push(source);
   while (!bfs_queue.empty()) {
      int city = bfs_queue.front();
      bfs_queue.pop();

      for (int & neighbour: tree_adjacency[city]) {
          if (distance[neighbour] != -1) {
              continue;
          }
          if (parent[neighbour] == city) {
              distance[neighbour] = distance[city] + deltas[neighbour];
          } else {
              distance[neighbour] = distance[city] - deltas[city];
          }
         bfs_queue.push(neighbour);
      }
   }

   return distance;
}


void decode(int num_cities, int num_hubs) {
   vector<vector<int>> tree_adjacency(num_cities);
   vector<int> parent(num_cities, -1);
   for (int i = 1; i < num_cities; i++) {
      int p = decode_in_bits(10);
      tree_adjacency[p].push_back(i);
      tree_adjacency[i].push_back(p);
      parent[i] = p;
   }

   vector<vector<int>> distances(num_hubs, vector<int>(num_cities));
   vector<int> deltas(num_cities);
   for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++) {
      int city = 1, aggregate_distance;
      while (city + 2 < num_cities) {
         aggregate_distance = decode_in_bits(5);
         for (int diff = 2; diff >= 0; diff--) {
           deltas[city + diff] = (aggregate_distance % 3) - 1;
           aggregate_distance /= 3;
         }
         city += 3;
      }
      while (city < num_cities) {
         deltas[city] = decode_in_bits(2) - 1;
         city++;
      }
      
      distances[hub_idx] = find_distances(hub_idx, tree_adjacency, deltas, parent);
   }

   for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++){
        for (int city = 0; city < num_cities; city++){
            hops(hub_idx, city, distances[hub_idx][city]);
        }
    }
}

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