#include "grader.h"
#include "encoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<ll>>g;
vector<vector<ll>>dist;
vector<vector<ll>>tree;
ll n,h,m;
void encode(int nv, int nh, int ne, int *v1, int *v2){
n=nv;
h=nh;
m=ne;
ll count=0;
g.assign(n,vector<ll>());
dist.assign(n,vector<ll>(n,INF));
tree.assign(n,vector<ll>());
for(int i=0;i<m;i++)
{
g[v1[i]].pb(v2[i]);
g[v2[i]].pb(v1[i]);
}
for(int i=0;i<n;i++)
{
vector<bool>vis(n,0);
vis[i]=1;
queue<ll>q;
q.push(i);
dist[i][i]=0;
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:g[curr])
if(!vis[x])
{
if(i==0)
tree[curr].pb(x);
q.push(x);
dist[i][x]=dist[i][curr]+1;
vis[x]=1;
}
}
}
queue<ll>q;
q.push(0);
ll left=n+2;
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
count++;
encode_bit(1);
ll temp=x;
ll l=0;
while((1<<l)<left)
l++;
for(int i=0;i<l;i++)
{
encode_bit(temp%2);
count++;
temp/=2;
}
q.push(x);
}
encode_bit(0);
count++;
}
for(int i=0;i<h;i++)
{
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
if(dist[i][curr] < dist[i][x])
{
encode_bit(1);
encode_bit(1);
}
if(dist[i][curr] == dist[i][x])
{
encode_bit(0);
encode_bit(0);
}
if(dist[i][curr] > dist[i][x])
{
encode_bit(0);
encode_bit(1);
}
count+=2;
q.push(x);
}
}
}
assert(count<85000);
return;
}
#include "grader.h"
#include "decoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<ll>>tree;
vector<ll>par;
ll n,h;
void decode(int nv, int nh) {
n=nv;
h=nh;
tree.assign(n,vector<ll>());
par.assign(n,-1);
queue<ll>q;
q.push(0);
ll left=n+2;
while(!q.empty())
{
ll get=decode_bit();
if(get==0)
q.pop();
else
{
ll curr=0;
ll l=0;
while((1<<l)<left)
l++;
left--;
for(int j=0;j<10;j++)
if(decode_bit())
curr+=(1<<j);
tree[q.front()].pb(curr);
par[curr]=q.front();
q.push(curr);
}
}
vector<vector<ll>>p(n,vector<ll>(n,0));
for(int i=0;i<h;i++)
{
vector<ll>dist(n,0);
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
ll id=2*decode_bit() + decode_bit();
if(id==0)
{
p[curr][x]=0;
p[x][curr]=0;
}
if(id==1)
{
p[curr][x]=-1;
p[x][curr]=1;
}
if(id==3)
{
p[curr][x]=1;
p[x][curr]=-1;
}
q.push(x);
}
}
ll now=i;
while(now!=0)
{
dist[par[now]]=dist[now]+p[now][par[now]];
now=par[now];
}
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
dist[x] = dist[curr] + p[curr][x];
q.push(x);
}
}
for(int j=0;j<n;j++)
hops(i,j,dist[j]);
}
}
