/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int N_MAX = 1000;
static const int H_MAX = 36;
static int N, H, E;
static int dist[H_MAX][N_MAX];
static int parent[N_MAX];
static vector <int> adj[N_MAX];
static vector <int> order;
void dfsRec (int u) {
order.push_back(u);
for (int v : adj[u]) {
if (parent[v] == -1) {
parent[v] = u;
dfsRec(v);
}
}
}
void dfs (int h) {
for (int u = 0; u < N; u++) {
parent[u] = -1;
}
parent[h] = h;
dfsRec(h);
}
#include "grader.h"
#include "encoder.h"
void encode_bit (int bit);
void encode_int (int val, int len) {
for (int bit = len - 1; bit >= 0; bit--) {
encode_bit((val >> bit) & 1);
}
}
void bfs (int h, int dist[]) {
for (int u = 0; u < N; u++) {
dist[u] = -1;
}
queue <int> q;
dist[h] = 0;
q.push(h);
while (q.empty() == false) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
void encode (int nv, int nh, int ne, int *v1, int *v2) {
N = nv; H = nh; E = ne;
for (int i = 0; i < E; i++) {
adj[v1[i]].push_back(v2[i]);
adj[v2[i]].push_back(v1[i]);
}
for (int u = 0; u < N; u++) {
sort(adj[u].begin(), adj[u].end());
}
for (int h = 0; h < H; h++) {
bfs(h, dist[h]);
}
dfs(0);
for (int u = 0; u < N; u++) {
adj[u].clear();
}
order.clear();
for (int u = 1; u < N; u++) {
encode_int(parent[u], 10);
adj[u].push_back(parent[u]);
adj[parent[u]].push_back(u);
}
for (int u = 0; u < N; u++) {
sort(adj[u].begin(), adj[u].end());
}
for (int h = 0; h < H; h++) {
dfs(h);
for (int i = 1; i < N; i++) {
int u = order[i];
encode_int(1 + (dist[h][u] - dist[h][parent[u]]), 2);
}
order.clear();
}
for (int u = 0; u < N; u++) {
adj[u].clear();
}
}
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int N_MAX = 1000;
static const int H_MAX = 36;
static int N, H, E;
static int dist[H_MAX][N_MAX];
static int parent[N_MAX];
static vector <int> adj[N_MAX];
static vector <int> order;
void dfsRec (int u) {
order.push_back(u);
for (int v : adj[u]) {
if (parent[v] == -1) {
parent[v] = u;
dfsRec(v);
}
}
}
void dfs (int h) {
for (int u = 0; u < N; u++) {
parent[u] = -1;
}
parent[h] = h;
dfsRec(h);
}
#include "grader.h"
#include "decoder.h"
int decode_bit ();
void hops (int a, int b, int d);
int decode_int (int len) {
int val = 0;
for (int bit = len - 1; bit >= 0; bit--) {
val |= (decode_bit() << bit);
}
return val;
}
void decode (int nv, int nh) {
N = nv; H = nh;
for (int u = 1; u < N; u++) {
parent[u] = decode_int(10);
adj[u].push_back(parent[u]);
adj[parent[u]].push_back(u);
}
for (int u = 0; u < N; u++) {
sort(adj[u].begin(), adj[u].end());
}
for (int h = 0; h < H; h++) {
dfs(h);
dist[h][h] = 0;
hops(h, h, dist[h][h]);
for (int i = 1; i < N; i++) {
int u = order[i];
dist[h][u] = dist[h][parent[u]] + (decode_int(2) - 1);
hops(h, u, dist[h][u]);
}
order.clear();
}
for (int u = 0; u < N; u++) {
adj[u].clear();
}
}
