#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "encoder.h"
void encode(int n, int h, int p, int a[], int b[]) {
vector<int> v[n];
for(int i = 0; i < p; i++) {
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
set<int> s;
s.insert(0);
int par[n] = {};
par[0] = 1;
vector<int> v2[n];
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
for(int i : v[x]) {
if(!par[i]) {
v2[x].push_back(i);
par[i] = x + 1;
s.insert(i);
}
}
sort(v2[x].begin(), v2[x].end());
}
for(int i = 1; i < n; i++) {
int x = par[i] - 1;
for(int j = 0; j < 10; j++)
encode_bit(((x & (1 << j)) > 0));
}
int ans[n][h];
for(int i = 0; i < n; i++) {
for(int j = 0; j < h; j++)
ans[i][j] = 1e9;
}
set<pair<int, pair<int, int>>> ss;
for(int i = 0; i < h; i++) {
ss.insert({0, {i, i}});
ans[i][i] = 0;
}
while(ss.size()) {
pair<int, pair<int, int>> p = *ss.begin();
ss.erase(ss.begin());
int x = p.second.first, hub = p.second.second;
int cost = p.first;
if(cost > ans[x][hub])
continue;
for(int i : v[x]) {
if(cost + 1 < ans[i][hub]) {
ans[i][hub] = cost + 1;
ss.insert({cost + 1, {i, hub}});
}
}
}
for(int i = 0; i < h; i++) {
int x = ans[0][i];
for(int j = 0; j < 10 && i; j++)
encode_bit(((x & (1 << j)) > 0));
s.insert(0);
while(s.size()) {
x = *s.begin();
s.erase(s.begin());
for(int j : v2[x]) {
s.insert(j);
if(j <= i)
continue;
int dif = ans[j][i] - ans[x][i];
if(dif == 0)
encode_bit(0);
else {
encode_bit(1);
if(dif == 1)
encode_bit(1);
else
encode_bit(0);
}
}
}
}
}
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "decoder.h"
void decode(int n, int h) {
vector<int> v[n];
for(int i = 1; i < n; i++) {
int x = 0;
for(int j = 0; j < 10; j++) {
if(decode_bit())
x += (1 << j);
}
v[x].push_back(i);
}
int ans[n][h];
for(int i = 0; i < h; i++) {
ans[i][i] = ans[0][i] = 0;
for(int j = 0; j < 10 && i; j++) {
if(decode_bit())
ans[0][i] += (1 << j);
}
set<int> s;
s.insert(0);
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
if(x >= i) {
hops(i, x, ans[x][i]);
if(x < h && x != i)
hops(x, i, ans[x][i]);
}
for(int j : v[x]) {
s.insert(j);
if(j <= i)
continue;
int dif = decode_bit();
if(dif) {
if(!decode_bit())
dif = -1;
}
ans[j][i] = ans[i][j] = ans[x][i] + dif;
}
}
}
}
