#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];
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);
}
}
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++) {
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]];
assert(abs(diff) <= 1);
// cout << i << ':' << distE[i] << ' ' << distE[paiE[i]] << endl;
if (diff == -1) send_int(0, 2);
else if (diff == 0) send_int(1, 2);
else send_int(2, 2);
}
// cout << endl;
}
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);
}
}
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++) {
for (int i=1; i<n; i++) {
int id = readInt(2);
int dist = ( // [i] - [pai[i]]
id == 0 ? -1 : (
id == 1 ? 0 : 1
)
);
adjDelta[i].emplace_back(pai[i], -dist);
adjDelta[pai[i]].emplace_back(i, dist);
// cout << i << '>' << pai[i] << ' ' << -dist << endl;
}
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;
}
}
