#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 3;
const int H = 36 + 3;
const int INF = 1e9;
static vector<int> adj[N];
static int n, h, m, par[N], d[N];
static bool vis[N];
void encode_num(int x){
for(int i = 9; i >= 0; --i)
encode_bit((x >> i) & 1);
}
void encode_diff(int diff){
if(diff == -1){
encode_bit(0);
encode_bit(0);
}
else if(!diff){
encode_bit(0);
encode_bit(1);
}
else{
encode_bit(1);
encode_bit(0);
}
}
void bfs_0(int u, int p = -1){
queue<int> q;
q.push(u);
vis[u] = true;
while(!q.empty()){
int v = q.front();
q.pop();
for(int to: adj[v])
if(!vis[to]){
vis[to] = true;
q.push(to);
par[to] = v;
}
}
}
void bfs(int u){
fill(d, d + n, INF);
queue<int> q;
q.push(u);
d[u] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(int to: adj[v])
if(d[to] == INF){
d[to] = d[u] + 1;
q.push(to);
}
}
/*cout << "d: ";
for(int i = 0; i < n; ++i)
cout << d[i] << " ";
cout << endl;
cout << "par: ";
for(int i = 1; i < n; ++i)
cout << par[i] << " ";
cout << endl;*/
for(int i = 1; i < n; ++i){
encode_diff(d[i] - d[par[i]]);
}
}
void encode(int _nv, int _nh, int _ne, int *v1, int *v2){
n = _nv, h =_nh, m = _ne;
for(int i = 0; i < n; ++i) adj[i].clear();
for(int i = 0; i < m; ++i){
adj[v1[i]].push_back(v2[i]);
adj[v2[i]].push_back(v1[i]);
}
fill(vis, vis + n, false);
bfs_0(0);
for(int i = 1; i < n; ++i)
encode_num(par[i]);
for(int i = 1; i < h; ++i)
bfs(i);
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 3;
const int H = 36 + 3;
static int n, h, par[N], d[N];
static vector<int> adj[N];
static bool vis[N];
int decode_diff(){
int bit1 = decode_bit();
int bit2 = decode_bit();
if(bit1) return 1;
if(bit2) return 0;
return -1;
}
int decode_num(){
int num = 0;
for(int i = 9; i >= 0; --i)
if(decode_bit())
num += (1 << i);
return num;
}
void dfs(int u){
hops(0, u, d[u]);
for(int to: adj[u]){
if(to == par[u]) continue;
d[to] = d[u] + 1;
dfs(to);
}
}
void dfs2(int hub, int u, int ans){
hops(hub, u, ans);
vis[u] = true;
for(int to: adj[u])
if(!vis[to]){
if(to == par[u]) dfs2(hub, to, ans - d[u]);
else dfs2(hub, to, ans + d[to]);
}
}
void decode(int _nv, int _nh) {
n = _nv, h = _nh;
if(n == 1){
hops(0, 0, 0);
return;
}
for(int i = 0; i < n; ++i) adj[i].clear();
for(int i = 1; i < n; ++i){
par[i] = decode_num();
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
d[0] = 0;
dfs(0);
for(int i = 1; i < h; ++i){
for(int j = 1; j < n; ++j)
d[j] = decode_diff();
fill(vis, vis + n, false);
dfs2(i, i, 0);
}
}
