Submission #231998

#	Time	Username	Problem	Language	Result	Execution time	Memory
231998		AlexLuchianov	Saveit (IOI10_saveit)	C++14	100 / 100	361 ms	11504 KiB

encoder

#include "grader.h"
#include <vector>
#include <cmath>
#include <cassert>
#include <queue>

int const nmax = 1000;
int const kmax = 36;

using ll = long long;

std::vector<int> g[1 + nmax];

std::vector<int> bfs(int n, int node){
  std::vector<int> dist(n);
  std::queue<int> q;
  q.push(node);
  dist[node] = 1;
  while(0 < q.size()){
    int node = q.front();
    q.pop();
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(dist[to] == 0){
        dist[to] = dist[node] + 1;
        q.push(to);
      }
    }
  }
  for(int i = 0; i < n; i++)
    dist[i]--;
  return dist;
}

std::vector<int> dist[1 + kmax];
int far[1 + nmax];

int const necessary = 35 / 5 * 8;

void push(ll number, int bits){
  for(int i = 0; i < bits; i++)
    encode_bit(0 < (number & (1LL << i)));
}

void encode(int n, int k, int m, int *v1, int *v2){
  for(int i = 0; i < m; i++){
    int x = v1[i];
    int y = v2[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for(int i = 0; i < k; i++)
    dist[i] = bfs(n, i);

  for(int i = 1;i < n; i++){
    for(int h = 0; h < g[i].size(); h++){
      int to = g[i][h];
      if(dist[0][to] + 1 == dist[0][i]) {
        far[i] = to;
        push(to, 10);
        break;
      }
    }
  }

  for(int i = 1; i < n; i++){
    ll number = 0;
    int par = far[i];
    for(int h = 1; h < k; h++)
      number = number * 3 + (dist[h][i] - dist[h][par]) + 1;
    push(number, necessary);
  }

  return;
}

decoder

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


using ll = long long;
int const necessary = 35 / 5 * 8;
int const kmax = 40;
int const nmax = 1000;

int _far[1 + nmax];

ll extract(int bits){
  ll result = 0;
  for(int i = 0; i < bits; i++)
    result += decode_bit() * (1LL << i);
  return result;
}
std::vector<int> _g[1 + nmax];
int cost[1 + kmax][1 + nmax];
int dp[1 + kmax][1 + nmax];

void mark(int node, int era){
  for(int h = 0; h < _g[node].size(); h++){
    int to = _g[node][h];
    dp[era][to] = dp[era][node] + cost[era][to];
    mark(to, era);
  }
}


void decode(int n, int k) {

  for(int i = 1;i < n; i++) {
    _far[i] = extract(10);
    _g[_far[i]].push_back(i);
  }

  for(int i = 1; i < n; i++){
    ll number = extract(necessary);
    cost[0][i] = 1;
    for(int h = k - 1; 0 < h; h--){
      cost[h][i] = number % 3 - 1;
      number /= 3;
    }
  }

  for(int h = 0; h < k; h++) {
    mark(0, h);
    for(int i = 0; i < n; i++)
      hops(h, i, dp[h][i] - dp[h][h]);
  }
}

Compilation message (stderr)

encoder.cpp: In function 'std::vector<int> bfs(int, int)':
encoder.cpp:22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[i].size(); h++){
                    ~~^~~~~~~~~~~~~

decoder.cpp: In function 'void mark(int, int)':
decoder.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < _g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~

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