#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> ad[1010];
int par[1010], dis[1010];
bool visited[1010];
void encode_num(int x, int b)
{
for(int i = 1; i <= b; i++){
encode_bit(x%2);
x >>= 1;
}
}
void dfs(int u)
{
visited[u] = 1;
for(int v : ad[u]) if(visited[v] == 0){
par[v] = u; dfs(v);
}
}
void encode_vec(vector<int> vec)
{
//There are 3^5 = 243 different combinations, which is smaller than 256 (1 byte)
int cur = 0, p = 1;
for(int i : vec){
cur += (i+1) * p; p *= 3;
}
/*cerr<<cur<<endl;
for(int i : vec) cerr<<i<<" ";
cerr<<endl;*/
encode_num(cur, 8);
}
void encode(int n, int hh, int m, int *v1, int *v2){
//Load the edges in the graph
for(int i = 0; i < m; i++){
ad[v1[i]].push_back(v2[i]);
ad[v2[i]].push_back(v1[i]);
}
//Send a spanning tree first
dfs(0);
for(int i = 1; i < n; i++) encode_num(par[i], 10);
//Then send the information
for(int p = 0; p < hh; p++){
memset(dis, 0x3f, sizeof(dis));
queue<int> w; dis[p] = 0; w.push(p);
while(w.size() > 0){
int u = w.front(); w.pop();
for(int v : ad[u]) if(dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1;
w.push(v);
}
}
//Encode the difference
vector<int> cur;
for(int i = 1; i < n; i++){
cur.push_back(dis[i] - dis[par[i]]);
if(cur.size() == 5){
encode_vec(cur);
cur.clear();
}
}
//We optimize by saving 5 numbers (in [-1, 1]) in a single byte
if(cur.size() > 0){
while(cur.size() < 5) cur.push_back(0);
encode_vec(cur);
}
}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
inline int flipbit(int num, int bit)
{
return num ^ (1 << bit);
}
int getnum(int b)
{
int cur = 0;
for(int i = 0; i < b; i++) if(decode_bit() == 1) cur = flipbit(cur, i);
return cur;
}
vector<int> getvec()
{
//Get the vector of 5 numbers from -1 to 1
int cur = getnum(8);
vector<int> ans;
for(int i = 1; i <= 5; i++){
ans.push_back(cur%3 - 1);
cur /= 3;
}
/*cerr<<"B"<<cur<<endl;
for(int i : ans) cerr<<i<<" ";
cerr<<endl;*/
return ans;
}
vector<array<int, 2>> adj[1010];
int parr[1010], pardif[1010], ans[1010];
bool visited2[1010];
void dfs_ans(int u)
{
visited2[u] = 1;
for(auto &[v, d] : adj[u]) if(visited2[v] == 0){
ans[v] = ans[u] + d;
dfs_ans(v);
}
visited2[u] = 0;
}
void decode(int n, int hh) {
//Reconstruct the spanning tree
for(int i = 1; i < n; i++) parr[i] = getnum(10);
//Solve for each hub
for(int i = 0; i < hh; i++){
for(int j = 0; j < n; j++) adj[j].clear();
//Get the dif information
for(int j = 1; j < n; j += 5){
vector<int> cur = getvec();
for(int k = j; k < j+5; k++) pardif[k] = cur[k-j];
}
for(int j = 1; j < n; j++){
adj[parr[j]].push_back({j, pardif[j]});
adj[j].push_back({parr[j], -pardif[j]});
}
//Calculate the actual value
ans[i] = 0; dfs_ans(i);
//Answer the question
for(int j = 0; j < n; j++) hops(i, j, ans[j]);
}
}
