#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using u8 = uint8_t;
void encode_byte(u8 bits) {
for (int i = 0; i < 8; ++i)
encode_bit((bits >> i) & 1);
}
void encode_varint(int x) {
do {
u8 byte = x & 0x7f;
x >>= 7;
if (x != 0)
byte |= 0x80;
encode_byte(byte);
} while (x != 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_varint(distances[i]);
}
}
return;
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using u8 = uint8_t;
u8 decode_byte() {
u8 byte = 0;
for (int i = 0; i < 8; ++i)
byte |= decode_bit() << i;
return byte;
}
int decode_varint() {
int result = 0;
u8 shift = 0;
while (true) {
u8 byte = decode_byte();
result |= (byte & 0x7f) << shift;
if ((byte & 0x80) == 0)
break;
shift += 7;
}
return result;
}
void decode(int nv, int nh) {
for (int hub = 0; hub < nh; hub++) {
for (int i = 0; i < nv; ++i) {
hops(hub, i, decode_varint());
}
}
}
