#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
namespace {
const int MAX_N = 1005;
vector <int> graph[MAX_N];
int parent[MAX_N], dist[MAX_N];
}
void encode(int nv, int nh, int ne, int *v1, int *v2) {
for(int i = 0; i < ne; i++) {
graph[v1[i]].push_back(v2[i]);
graph[v2[i]].push_back(v1[i]);
}
for(int i = 0; i < nv; i++) {
dist[i] = -1;
}
queue <int> q;
q.push(0);
dist[0] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
for(int i = 1; i < nv; i++) {
for(int k = 0; k < 10; k++) {
if((1<<k) & parent[i]) {
encode_bit(1);
}
else {
encode_bit(0);
}
}
}
for(int h = 1; h < nh; h++) {
for(int i = 0; i < nv; i++) {
dist[i] = -1;
}
queue <int> q;
q.push(h);
dist[h] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
for(int i = 1; i < nv; i++) {
if(dist[i] == dist[parent[i]]) {
encode_bit(0);
}
else {
encode_bit(1);
if(dist[i] < dist[parent[i]]) {
encode_bit(1);
}
else {
encode_bit(0);
}
}
}
}
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
namespace {
const int MAX_N = 1005;
vector <int> graph[MAX_N];
int parent[MAX_N];
int dist[MAX_N], W[MAX_N][MAX_N];
}
void decode(int nv, int nh) {
for(int i = 1; i < nv; i++) {
int p = 0;
for(int k = 0; k < 10; k++) {
p += (1<<k) * decode_bit();
}
parent[i] = p;
graph[p].push_back(i);
graph[i].push_back(p);
}
for(int i = 0; i < nv; i++) {
dist[i] = -1;
}
queue <int> q;
q.push(0);
dist[0] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
for(int i = 0; i < nv; i++) {
hops(0, i, dist[i]);
}
for(int h = 1; h < nh; h++) {
for(int i = 1; i < nv; i++) {
if(decode_bit() == 0) {
W[i][parent[i]] = 0;
W[parent[i]][i] = 0;
}
else {
if(decode_bit() == 1) {
W[i][parent[i]] = 1;
W[parent[i]][i] = -1;
}
else {
W[i][parent[i]] = -1;
W[parent[i]][i] = 1;
}
}
}
for(int i = 0; i < nv; i++) {
dist[i] = -1;
}
queue <int> q;
q.push(h);
dist[h] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + W[u][v];
q.push(v);
}
}
}
for(int i = 0; i < nv; i++) {
hops(h, i, dist[i]);
}
}
}
