#include "grader.h"
#include "encoder.h"
# include <iostream>
# include <vector>
# include <algorithm>
# include <queue>
using namespace std;
const int MAX=1e3+11,INF=1e9;
const int B=10,K=58;
int n,m,H;
vector<int> adj[MAX];
int dist[MAX][MAX];
int up[MAX];
void bfs(int start)
{
for(int i=0;i<n;i++)
{
dist[start][i]=INF;
up[i]=-1;
}
dist[start][start]=0;
up[start]=-1;
queue<int> q;
q.push(start);
while(q.size()>0)
{
int curr=q.front();
q.pop();
for(int nxt: adj[curr])
{
if(dist[start][nxt]>dist[start][curr]+1)
{
dist[start][nxt]=dist[start][curr]+1;
up[nxt]=curr;
q.push(nxt);
}
}
}
}
void encode_num(long long x, int cnt)
{
vector<int> v;
for(int i=0;i<cnt;i++)
{
v.push_back(x%2);
x/=2;
}
reverse(v.begin(),v.end());
for(int b: v) encode_bit(b);
}
void reset()
{
for(int i=0;i<n;i++)
{
adj[i].clear();
}
}
void encode(int N, int _H, int P, int *a, int *b)
{
n=N;m=P;H=_H;
reset();
for(int i=0;i<m;i++)
{
int u=a[i],v=b[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<H;i++) bfs(i);
bfs(0);
for(int i=1;i<n;i++) encode_num(up[i],B);
for(int i=0;i<H;i++) encode_num(dist[i][0],B);
for(int i=1;i<n;i++)
{
long long x=0;
for(int j=H-1;j>=0;j--)
{
x*=3;
long long delta=dist[j][i]-dist[j][up[i]]+1;
x+=delta;
}
encode_num(x,K);
}
}
#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
# include <algorithm>
using namespace std;
//namespace nz
//{
const int MAX=1e3+11;
const int B=10,K=58;
int n,H;
vector<int> adj[MAX];
int dist[MAX][MAX];
long long decode_num(int cnt)
{
long long x=0;
for(int i=0;i<cnt;i++)
{
x*=2;
x+=decode_bit();
}
return x;
}
void dfs(int curr, int par)
{
if(par!=-1)
{
for(int j=0;j<H;j++) dist[j][curr]+=dist[j][par];
}
for(int j=0;j<H;j++) hops(j,curr,dist[j][curr]);
for(int nxt: adj[curr]) dfs(nxt,curr);
}
void reset()
{
for(int i=0;i<n;i++)
{
adj[i].clear();
for(int j=0;j<H;j++) dist[j][i]=0;
}
}
void decode(int _n, int _H)
{
n=_n;H=_H;
reset();
for(int i=1;i<n;i++)
{
int x=decode_num(B);
adj[x].push_back(i);
}
for(int i=0;i<H;i++) dist[i][0]=decode_num(B);
for(int i=1;i<n;i++)
{
long long x=decode_num(K);
for(int j=0;j<H;j++)
{
long long delta=x%3-1;
x/=3;
dist[j][i]=delta;
}
}
dfs(0,-1);
}
//}
