#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
const int MAXH = 36;
vector<int> adjE[MAXN];
bool visE[MAXN];
int distE[MAXN], paiE[MAXN], lastDistE[MAXN], diffs[MAXN];
int n;
void bfs(int src, bool updatePai) {
for (int i=0; i<n; i++) {
visE[i] = false;
}
visE[src] = true; distE[src] = 0;
queue<int> visit; visit.push(src);
while (!visit.empty()) {
int v = visit.front(); visit.pop();
for (int viz : adjE[v]) {
if (visE[viz]) continue;
visE[viz] = true;
distE[viz] = distE[v] + 1;
if (updatePai) {
paiE[viz] = v;
// cout << "pai: " << v << " de " << viz << endl;
}
visit.push(viz);
}
}
}
void send_int(int val, int bits) {
// cout << "envia" << val << endl;
for (int b=0; b<bits; b++) {
encode_bit(((1 << b) & val) != 0);
}
}
int calculate_encode(vector<int> grp) {
int code = 0;
for (int i=0, pot=1; i<5; i++, pot*=3) {
code += grp[i] * pot;
// cerr << '(' << grp[i] << ' ' << pot << ')';
}
// cerr << "code=" << code << '\n';
return code;
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
n = nv;
for (int i=0; i<ne; i++) {
int u = v1[i], v = v2[i];
adjE[u].push_back(v);
adjE[v].push_back(u);
}
bfs(0, true);
for (int i=1; i<n; i++) {
// cout << paiE[i] << endl;
send_int(paiE[i], 10);
}
for (int h=1; h<nh; h++) {
// cerr << "\n\n\nenvia hub " << h << endl;
for (int i=0; i<n; i++) lastDistE[i] = distE[i];
bfs(h, false);
for (int i=1; i<n; i++) {
int diff = distE[i] - distE[paiE[i]];
diffs[i] = diff;
}
for (int i=1; i<n; i+=5) {
vector<int> grp(5, 0);
for (int j=0; j<5 and i+j<n; j++) {
grp[j] = diffs[i+j] + 1;
// // cerr << grp[j] << ' ';
}
send_int(calculate_encode(grp), 8);
}
}
return;
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
vector<int> adj[MAXN];
vector<pair<int, int>> adjDelta[MAXN];
bool vis[MAXN];
int dist[MAXN], pai[MAXN];
int readInt(int bits) {
int res = 0;
for (int b=0; b<bits; b++) {
if (decode_bit()) res += (1 << b);
}
// cout << "recebe " << res << endl;
return res;
}
void dfs(int v) {
for (int viz : adj[v]) {
dist[viz] = dist[v] + 1;
dfs(viz);
}
}
void dfsDelta(int v) {
vis[v] = true;
for (auto [viz, delta] : adjDelta[v]) {
if (vis[viz]) continue;
dist[viz] = dist[v] + delta;
dfsDelta(viz);
}
}
vector<int> decode_grp(int code) {
vector<int> grp(5, 0);
for (int i=4, pot=81; i>=0; i--, pot /= 3) {
grp[i] = code / pot;
code %= pot;
}
return grp;
}
void decode(int nv, int nh) {
int n = nv;
for (int i=1; i<n; i++) {
pai[i] = readInt(10);
adj[pai[i]].push_back(i);
}
dist[0] = 0;
dfs(0);
for (int i=0; i<n; i++) hops(0, i, dist[i]);
for (int h=1; h<nh; h++) {
// cerr << "\n\n\nrecebe hub " << h << endl;
for (int i=1; i<n; i+=5) {
int code = readInt(8);
vector<int> grp = decode_grp(code);
for (int j=0; j<5 and i + j < n; j++) {
int dist = grp[j] - 1;
// cerr << grp[j] << ' ';
adjDelta[i+j].emplace_back(pai[i+j], -dist);
adjDelta[pai[i+j]].emplace_back(i+j, dist);
}
}
dist[h] = 0;
dfsDelta(h);
for (int i=0; i<n; i++) hops(h, i, dist[i]);
for (int i=0; i<n; i++) {
vis[i] = false;
adjDelta[i].clear();
}
// cout << endl << endl;
}
}
