Submission #1126850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126850		BlancaHM	Saveit (IOI10_saveit)	C++17	100 / 100	66 ms	5952 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <queue>
#include <vector>
using namespace std;

vector<int> shortest_path_to_all_cities(int source, vector<vector<int>> & adjacency) {
  // Calculate length of shortest path from source to all cities in graph.
  int num_cities = (int) adjacency.size();
  vector<int> distances(num_cities, num_cities + 1);
  distances[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: adjacency[city]) {
      if (distances[neighbour] > distances[city] + 1) {
        distances[neighbour] = distances[city] + 1;
        bfs_queue.push(neighbour);
      }
    }
  }
  return distances;
}


vector<vector<int>> calculate_distances_to_hubs(
    vector<vector<int>> & adjacency, int num_hubs
) {
  // Calculate length of shortest paths from all hubs to all cities in graph.
  vector<vector<int>> distances(num_hubs);
  for (int i = 0; i < num_hubs; i++) {
    distances[i] = shortest_path_to_all_cities(i, adjacency);
  }
  return distances;
}


vector<int> define_parent(vector<vector<int>> & adjacency) {
  // Run BFS from city 0 to define BFS tree for the graph.
  vector<int> parent(adjacency.size(), -1);
  queue<int> bfs_queue;
  bfs_queue.push(0);
  parent[0] = -2;
  while (!bfs_queue.empty()) {
    int city = bfs_queue.front();
    bfs_queue.pop();
    for (int & neighbour: adjacency[city]) {
      if (parent[neighbour] == -1) {
        parent[neighbour] = city;
        bfs_queue.push(neighbour);
      }
    }
  }
  parent[0] = -1;
  return parent;
}


void encode_in_bits(int number, int num_bits) {
  // Encode a decimal number in num_bits binary columns.
  vector<int> bits(num_bits);
  for (int idx = num_bits - 1; idx >= 0; idx--) {
    bits[num_bits - idx - 1] = number / (1 << idx);
    number %= (1 << idx);
  }
  for (int i = 0; i < num_bits; i++) {
    encode_bit((bool) bits[i]);
  }
}


void encode(int num_cities, int num_hubs, int num_hops, int *v1, int *v2){
  vector<vector<int>> adjacency(num_cities);
  for (int i = 0; i < num_hops; i++) {
    adjacency[v1[i]].push_back(v2[i]);
    adjacency[v2[i]].push_back(v1[i]);
  }
  vector<vector<int>> distances = calculate_distances_to_hubs(adjacency, num_hubs);
  vector<int> parent = define_parent(adjacency);

  for (int i = 1; i < num_cities; i++) {
    encode_in_bits(parent[i], 10);
  }

  int city, distances_delta, aggregate_distance;
  for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++) {
    city = 1;
    while (city + 2 < num_cities) {
      aggregate_distance = 0;
      for (int diff = 0; diff < 3; diff++) {
        distances_delta = distances[hub_idx][city + diff] - distances[hub_idx][parent[city + diff]] + 1;
        aggregate_distance = 3 * aggregate_distance + distances_delta;
      }
      encode_in_bits(aggregate_distance, 5);
      city += 3;
    }
    while (city < num_cities) {
      distances_delta = distances[hub_idx][city] - distances[hub_idx][parent[city]] + 1;
      encode_in_bits(distances_delta, 2);
      city++;
    }
  }
}

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