oj.uz

Submission #1118016

# Submission time Handle Problem Language Result Execution time Memory
1118016 2024-11-24T17:27:06 Z BlancaHM Saveit (IOI10_saveit) C++14
0 / 100
 170 ms 6040 KB 
#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);
  while (!bfs_queue.empty()) {
    int city = bfs_queue.front();
    bfs_queue.pop();
    for (int & neighbour: adjacency[city]) {
      if (parent[neighbour] == -2) {
        parent[neighbour] = city;
        bfs_queue.push(neighbour);
      }
    }
  }
  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 & bit: bits) {
    encode_bit(bit);
  }
}


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);
  }

  for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++) {
    encode_in_bits(distances[hub_idx][0], 10);
    for (int city = 1; city < num_cities; city++) {
      if (distances[hub_idx][city] == distances[hub_idx][parent[city]]) {
        encode_in_bits(0, 2);
      } else if (distances[hub_idx][city] == distances[hub_idx][parent[city]] + 1) {
        encode_in_bits(1, 2);
      } else {
        encode_in_bits(2, 2);
      }
    }
  }
}

#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] = 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_distance, vector<vector<int>> & tree_adjacency, vector<int> & deltas) {
   vector<int> distance(tree_adjacency.size());
   distance[0] = source_distance;

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

      for (int & neighbour: tree_adjacency[city]) {
         distance[neighbour] = distance[city] + deltas[neighbour];
         bfs_queue.push(neighbour);
      }
   }

   return distance;
}


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

   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 source_distance = decode_in_bits(10);
      for (int i = 1; i < num_cities; i++) {
         deltas[i] = decode_in_bits(2);
      }
      distances[hub_idx] = find_distances(source_distance, tree_adjacency, deltas);
   }

   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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 6040 KB encode_bit(b) wrong parameter
2 Incorrect 2 ms 780 KB encode_bit(b) wrong parameter
3 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
4 Incorrect 2 ms 768 KB encode_bit(b) wrong parameter
5 Incorrect 6 ms 1280 KB encode_bit(b) wrong parameter
6 Incorrect 5 ms 1284 KB encode_bit(b) wrong parameter
7 Incorrect 23 ms 1776 KB encode_bit(b) wrong parameter
8 Incorrect 4 ms 1036 KB encode_bit(b) wrong parameter
9 Incorrect 6 ms 1276 KB encode_bit(b) wrong parameter
10 Incorrect 8 ms 1296 KB encode_bit(b) wrong parameter
11 Incorrect 5 ms 1280 KB encode_bit(b) wrong parameter
12 Incorrect 4 ms 1024 KB encode_bit(b) wrong parameter
13 Incorrect 26 ms 1756 KB encode_bit(b) wrong parameter
14 Incorrect 4 ms 1284 KB encode_bit(b) wrong parameter
15 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
16 Incorrect 29 ms 1780 KB encode_bit(b) wrong parameter
17 Incorrect 20 ms 1788 KB encode_bit(b) wrong parameter
18 Incorrect 27 ms 2052 KB encode_bit(b) wrong parameter
19 Incorrect 15 ms 1532 KB encode_bit(b) wrong parameter
20 Incorrect 39 ms 2104 KB encode_bit(b) wrong parameter
21 Incorrect 44 ms 2264 KB encode_bit(b) wrong parameter
22 Incorrect 26 ms 1932 KB encode_bit(b) wrong parameter
23 Incorrect 45 ms 2496 KB encode_bit(b) wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 6040 KB encode_bit(b) wrong parameter
2 Incorrect 2 ms 780 KB encode_bit(b) wrong parameter
3 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
4 Incorrect 2 ms 768 KB encode_bit(b) wrong parameter
5 Incorrect 6 ms 1280 KB encode_bit(b) wrong parameter
6 Incorrect 5 ms 1284 KB encode_bit(b) wrong parameter
7 Incorrect 23 ms 1776 KB encode_bit(b) wrong parameter
8 Incorrect 4 ms 1036 KB encode_bit(b) wrong parameter
9 Incorrect 6 ms 1276 KB encode_bit(b) wrong parameter
10 Incorrect 8 ms 1296 KB encode_bit(b) wrong parameter
11 Incorrect 5 ms 1280 KB encode_bit(b) wrong parameter
12 Incorrect 4 ms 1024 KB encode_bit(b) wrong parameter
13 Incorrect 26 ms 1756 KB encode_bit(b) wrong parameter
14 Incorrect 4 ms 1284 KB encode_bit(b) wrong parameter
15 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
16 Incorrect 29 ms 1780 KB encode_bit(b) wrong parameter
17 Incorrect 20 ms 1788 KB encode_bit(b) wrong parameter
18 Incorrect 27 ms 2052 KB encode_bit(b) wrong parameter
19 Incorrect 15 ms 1532 KB encode_bit(b) wrong parameter
20 Incorrect 39 ms 2104 KB encode_bit(b) wrong parameter
21 Incorrect 44 ms 2264 KB encode_bit(b) wrong parameter
22 Incorrect 26 ms 1932 KB encode_bit(b) wrong parameter
23 Incorrect 45 ms 2496 KB encode_bit(b) wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 6040 KB encode_bit(b) wrong parameter
2 Incorrect 2 ms 780 KB encode_bit(b) wrong parameter
3 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
4 Incorrect 2 ms 768 KB encode_bit(b) wrong parameter
5 Incorrect 6 ms 1280 KB encode_bit(b) wrong parameter
6 Incorrect 5 ms 1284 KB encode_bit(b) wrong parameter
7 Incorrect 23 ms 1776 KB encode_bit(b) wrong parameter
8 Incorrect 4 ms 1036 KB encode_bit(b) wrong parameter
9 Incorrect 6 ms 1276 KB encode_bit(b) wrong parameter
10 Incorrect 8 ms 1296 KB encode_bit(b) wrong parameter
11 Incorrect 5 ms 1280 KB encode_bit(b) wrong parameter
12 Incorrect 4 ms 1024 KB encode_bit(b) wrong parameter
13 Incorrect 26 ms 1756 KB encode_bit(b) wrong parameter
14 Incorrect 4 ms 1284 KB encode_bit(b) wrong parameter
15 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
16 Incorrect 29 ms 1780 KB encode_bit(b) wrong parameter
17 Incorrect 20 ms 1788 KB encode_bit(b) wrong parameter
18 Incorrect 27 ms 2052 KB encode_bit(b) wrong parameter
19 Incorrect 15 ms 1532 KB encode_bit(b) wrong parameter
20 Incorrect 39 ms 2104 KB encode_bit(b) wrong parameter
21 Incorrect 44 ms 2264 KB encode_bit(b) wrong parameter
22 Incorrect 26 ms 1932 KB encode_bit(b) wrong parameter
23 Incorrect 45 ms 2496 KB encode_bit(b) wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 6040 KB encode_bit(b) wrong parameter
2 Incorrect 2 ms 780 KB encode_bit(b) wrong parameter
3 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
4 Incorrect 2 ms 768 KB encode_bit(b) wrong parameter
5 Incorrect 6 ms 1280 KB encode_bit(b) wrong parameter
6 Incorrect 5 ms 1284 KB encode_bit(b) wrong parameter
7 Incorrect 23 ms 1776 KB encode_bit(b) wrong parameter
8 Incorrect 4 ms 1036 KB encode_bit(b) wrong parameter
9 Incorrect 6 ms 1276 KB encode_bit(b) wrong parameter
10 Incorrect 8 ms 1296 KB encode_bit(b) wrong parameter
11 Incorrect 5 ms 1280 KB encode_bit(b) wrong parameter
12 Incorrect 4 ms 1024 KB encode_bit(b) wrong parameter
13 Incorrect 26 ms 1756 KB encode_bit(b) wrong parameter
14 Incorrect 4 ms 1284 KB encode_bit(b) wrong parameter
15 Incorrect 4 ms 1280 KB encode_bit(b) wrong parameter
16 Incorrect 29 ms 1780 KB encode_bit(b) wrong parameter
17 Incorrect 20 ms 1788 KB encode_bit(b) wrong parameter
18 Incorrect 27 ms 2052 KB encode_bit(b) wrong parameter
19 Incorrect 15 ms 1532 KB encode_bit(b) wrong parameter
20 Incorrect 39 ms 2104 KB encode_bit(b) wrong parameter
21 Incorrect 44 ms 2264 KB encode_bit(b) wrong parameter
22 Incorrect 26 ms 1932 KB encode_bit(b) wrong parameter
23 Incorrect 45 ms 2496 KB encode_bit(b) wrong parameter