Submission #573249

#	Time	Username	Problem	Language	Result	Execution time	Memory
573249		Vanilla	Saveit (IOI10_saveit)	C++17	50 / 100	250 ms	12584 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const int maxn = 1002;
vector <int> ad [maxn];
int dist [36][maxn];

void bfs (int x) {
  queue <int> q;
  q.push(x);
  dist[x][x] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v: ad[u]) {
      if (dist[x][u] + 1 < dist[x][v]) {
        dist[x][v] = dist[x][u] + 1;
        q.push(v);
      }
    }
  }
}

void encode(int N, int H, int P, int *v1, int *v2){
  for (int i = 0; i < P; i++){
    ad[v1[i]].push_back(v2[i]);
    ad[v2[i]].push_back(v1[i]);
  }
  for (int i = 0; i < H; i++){
    for (int j = 0; j < maxn; j++){
      dist[i][j] = 1000;
    }
  }
  
  for (int i = 0; i < H; i++){
    bfs(i);
  }
  for (int i = 0; i < H; i++){
    for (int k = 0; k < N; k++){
      for (int j = 0; j < 10; j++){
        encode_bit(!!(dist[i][k] & (1 << j)));
      }
    }
  }
  return;
}

decoder

#include "grader.h"
#include "decoder.h"

void decode(int N, int H) {
   for (int i = 0; i < H; i++){
      for (int j = 0; j < N; j++){
         int val = 0;
         for (int k = 0; k < 10; k++){
            val+=(1 << k) * decode_bit();
         }
         hops(i,j,val);
      }
   }
}

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