#include "grader.h"
#include "encoder.h"
#include"bits/stdc++.h"
using namespace std;
void encode(int n, int h, int p, int *v1, int *v2){
vector<int> adj[n];
for (int i = 0 ; i < p ; i++) {
adj[v1[i]].push_back(v2[i]);
adj[v2[i]].push_back(v1[i]);
}
int par[n];
{
queue<int> q;
vector<bool> vis(n);
q.push(0);
while (q.size()) {
auto cur = q.front();
q.pop();
for (int j : adj[cur]) {
if (!vis[j]) {
vis[j] = 1;
par[j] = cur;
q.push(j);
}
}
}
}
auto sendnum = [&](int x) {
for (int k = 0 ; k < 10 ; k++) {
encode_bit(!!(x & (1 << k)));
}
};
for (int i = 1 ; i < n ; i++) sendnum(par[i]);
for (int i = 1 ; i < h ; i++) {
queue<int> q;
vector<int> dis(n, -1);
dis[i] = 0;
q.push(i);
while (q.size()) {
auto cur = q.front();
q.pop();
for (int j : adj[cur]) {
if (dis[j] == -1) {
dis[j] = dis[cur] + 1;
q.push(j);
}
}
}
for (int i = 1 ; i < n ; i++) {
int x = dis[i] - dis[par[i]];
if (x == 1) encode_bit(1), encode_bit(1);
else if (x == -1) encode_bit(0);
else encode_bit(1), encode_bit(0);
}
}
}
#include "grader.h"
#include "decoder.h"
#include "bits/stdc++.h"
using namespace std;
void decode(int n, int h) {
vector<int> adj[n];
int par[n];
auto getnum = [&]() {
int ret = 0;
for (int k = 0 ; k < 10 ; k++) {
ret |= (1 << k)*decode_bit();
}
return ret;
};
for (int i = 1 ; i < n ; i++) {
int x = getnum();
par[i] = x;
adj[i].push_back(x);
adj[x].push_back(i);
}
{
queue<int> q;
vector<int> dis(n, -1);
dis[0] = 0;
q.push(0);
while (q.size()) {
auto cur = q.front();
q.pop();
for (int j : adj[cur]) {
if (dis[j] == -1) {
dis[j] = dis[cur] + 1;
q.push(j);
}
}
}
for (int i = 0 ; i < n ; i++) {
hops(0, i, dis[i]);
}
}
int w[n][n];
for (int i = 1 ; i < h ; i++) {
for (int j = 1 ; j < n ; j++) {
int v;
if (decode_bit()) {
if (decode_bit()) v = 1;
else v = 0;
} else {
v = -1;
}
w[par[j]][j] = v;
w[j][par[j]] = -v;
}
queue<int> q;
vector<int> dis(n, -1e9);
dis[i] = 0;
q.push(i);
while (q.size()) {
auto cur = q.front();
q.pop();
for (int j : adj[cur]) {
if (dis[j] == -1e9) {
dis[j] = dis[cur] + w[cur][j];
q.push(j);
}
}
}
for (int j = 0 ; j < n ; j++) {
hops(i, j, dis[j]);
}
}
}
