Submission #1144693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144693		otesunki	Saveit (IOI10_saveit)	C++20	25 / 100	1139 ms	71460 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

void encode_fib(unsigned x) {
  while (x--)
    encode_bit(1);
  encode_bit(0);
}

template<typename T> using Vec = std::vector<T>;

Vec<int> bfs(int hub, int nv, const Vec<Vec<int>>& giraffe) {
    const int invalid = -1;

    Vec<int> dist(nv);
    std::fill(dist.begin(), dist.end(), invalid);

    std::queue<std::pair<int, int>> q; q.emplace(hub, 0);

    while (!q.empty()) {
        auto [u, distance] = q.front(); q.pop();
        if (dist[u] != invalid) continue;
        dist[u] = distance++;
        for (const auto& v : giraffe[u]) {
            q.emplace(v, distance);
        }
    }

    return dist;
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    Vec<Vec<int>> giraffe(nv);
    for (int i = 0; i < ne ; ++i) {
        int u = v1[i];
        int v = v2[i];
        giraffe[u].push_back(v);
        giraffe[v].push_back(u);
    }

    for (int hub = 0; hub < nh; hub++) {
        Vec<int> distances = bfs(hub, nv, giraffe);
        for (int i = 0; i < nv; ++i) {
            encode_fib(distances[i]);
        }
    }

    return;
}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

unsigned decode_fib(void) {
  unsigned tally = 0;
  while (decode_bit())
    ++tally;
  return tally;
}

void decode(int nv, int nh) {
   for (int hub = 0; hub < nh; hub++) {
      for (int i = 0; i < nv; ++i) {
         hops(hub, i, decode_fib());
      }
   }
}

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