#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1005, maxh = 40;
int p;
vector < int > g[maxn];
vector < pair < int, int > > edges;
int distt[maxh][maxn], parr[maxn];
void bfs(int start, int n)
{
// cout << "run " << start << endl;
for (int i = 0; i < n; ++ i)
distt[start][i] = -1;
queue < int > q;
q.push(start);
distt[start][start] = 0;
while(!q.empty())
{
int w = q.front();
// cout << "w is " << w << endl;
q.pop();
for (auto nb: g[w])
{
// cout << nb << endl;
if(distt[start][nb] != -1)continue;
distt[start][nb] = distt[start][w] + 1;
// cout << "?"<< distt[start][nb] << endl;
if(start == 0)parr[nb] = w;
q.push(nb);
}
}
}
int curr_bit = 0;
void code_bits(int x)
{
for (int i = 0; i < 10; ++ i)
{
if(x & (1 << i))
{
encode_bit(1);
}
else encode_bit(0);
curr_bit++;
}
}
void code_bits3(int x)
{
if(x == 0)encode_bit(0);
else
{
encode_bit(1);
if(x == 1)encode_bit(0);
else encode_bit(1);
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
// cout << "in encode" << endl;
int n = nv;
int h = nh;
p = ne;
for (int i = 0; i < p; ++ i)
{
int u = v1[i];
int v = v2[i];
edges.pb(make_pair(u, v));
g[u].pb(v);
g[v].pb(u);
// cout << u << " " << v<<endl;
}
for (int i = 0; i < h; ++ i)
bfs(i, n);
for (int i = 1; i < n; ++ i)
{
//if(!parr[i])continue;
//cout << i << " "<<parr[i] << endl;
code_bits(parr[i]);
}
for (int i = 1; i < h; ++ i)
{
for (int j = 1; j < n; ++ j)
{
// cout << "dist btween " << i << " " << j << " is " << distt[i][j] << endl;
if(distt[i][j] == distt[i][parr[j]])code_bits3(0);
else if(distt[i][j] == distt[i][parr[j]] - 1)code_bits3(1);
else code_bits3(2);
}
}
// cout << "ended " << endl;
return;
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxnn = 1005;
int n, hh;
int par[maxnn];
vector < int > u[maxnn];
int dist[maxnn][maxnn], change[maxnn][maxnn];
void dfs(int beg, int d)
{
dist[0][beg] = d-1;
dist[beg][0] = d-1;
for (auto nb: u[beg])
{
dfs(nb, d + 1);
}
}
void solve(int curr)
{
for (int i = 0; i < hh; ++ i)
hops(i, curr, dist[i][curr]);
for (auto child: u[curr])
{
for (int i = 0; i < hh; ++ i)
{
//cout << i << " " << hh << endl;
dist[i][child] = dist[i][curr] + change[i][child];
}
solve(child);
}
}
void decode(int nv, int nh)
{
n = nv;
hh = nh;
for (int i = 1; i < n; ++ i)
{
for (int bit = 0; bit < 10; ++ bit)
{
int curr = decode_bit();
if(curr)par[i] = (par[i] | (1 << bit));
}
//cout << i << " !! " << par[i] << endl;
}
for (int i = 1; i < n; ++ i)
{
u[par[i]].pb(i);
}
dfs(0, 1);
// cout << "dfs ended " << endl;
for (int i = 1; i < hh; ++ i)
{
for (int j = 1; j < n; ++ j)
{
//cout << i << " " << j << endl;
int fbit, sbit;
fbit = decode_bit();
int number = 0;
if(!fbit)number = 0;
else
{
sbit = decode_bit();
if(sbit)number = 2;
else number = 1;
}
if(number == 0)change[i][j] = 0;
else if(number == 1)change[i][j] = -1;
else change[i][j] = 1;
// cout << fbit << ", " << sbit << "-> " << number << endl;
// cout << "change " << i << " " << j << " -> " << number << endl;
}
}
// cout << "solve starting " << endl;
solve(0);
}
