#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
vector<int>adj[1001];
int dis[1001],par[1001], j;
void reset(int n){
j = 0;
for(int i = 0; i < n; i++) {
adj[i].clear();
dis[i] = INT_MAX;
}
}
void encode(int n, int h, int p, int a[], int b[]){
reset(n);
for(int i = 0; i < p; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
dis[0] = par[0] = 0;
vector<int>d = {0};
while(d.size()){
for(auto s: adj[d[j]]){
if(dis[s] == INT_MAX){
dis[s] = dis[d[j]] + 1;
par[s] = d[j];
d.push_back(s);
}
}
j++;
}
for(int i = 1; i < n; i++){
for(int k = 0; k < 10; k++){
if(par[i] & (1 << k)) encode_bit(1);
else encode_bit(0);
}
}
for(int i = 1; i < h; i++){
vector<int>pc(n, INT_MAX);
pc[i] = j = 0;
vector<int>b = {i};
while(b.size()){
for(auto s:adj[b[j]]){
if(pc[s] == INT_MAX){
pc[s] = pc[b[j]] + 1;
b.push_back(s);
}
}
j++;
}
for(int i = 1; i < n; i++){
int diff = pc[i] - pc[par[i]];
if(diff != 0){
encode_bit(1);
if(diff < 0) encode_bit(1);
else encode_bit(0);
}else{
encode_bit(0);
}
}
}
}
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
vector<int>adj[1001];
int dis[1001],p[1001],diff[1001][1001],j;
void reset(int n){
j = 0;
for(int i = 0; i < n; i++) {
adj[i].clear();
dis[i] = INT_MAX;
}
for(int i = 0; i < n; i++){
for(int k = 0; k < n; k++) diff[i][k] = 0;
}
}
void decode(int n, int h){
reset(n);
for(int i = 1; i < n; i++){
int parent = 0;
for(int k = 0; k < 10; k++){
if(decode_bit()) parent += (1 << k);
}
adj[i].push_back(parent);
adj[parent].push_back(i);
}
dis[0] = j = 0;
vector<int>b = {0};
while(b.size()){
for(auto s: adj[b[j]]){
if(dis[s] == INT_MAX){
dis[s] = dis[b[j]] + 1;
}
}
j++;
}
for(int i = 0; i < n; i++) hops(0,i, dis[i]);
for(int i = 1; i < h; i++){
for(int k = 1; k < n; k++){
int x = decode_bit();
if(x == 0){
diff[k][p[k]] = diff[p[k]][k] = 0;
}else{
if(decode_bit()){
diff[k][p[k]] = 1;
diff[p[k]][k] = -1;
}else{
diff[p[k]][k] = 1;
diff[k][p[k]] = -1;
}
}
vector<int>pc(n, INT_MAX);
pc[i] = j = 0;
vector<int>b = {i};
while(b.size()){
for(auto s:adj[b[j]]){
if(pc[s] == INT_MAX){
pc[s] = pc[b[j]] + diff[b[j]][s];
b.push_back(s);
}
}
j++;
}
for(int t = 0; t < n; t++){
hops(i,t,pc[t]);
}
}
}
}
