#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const int MAXN = 1e3 + 10;
static int pai[MAXN];
static int dist[MAXN][MAXN], marc[MAXN][MAXN];
static vector<int> adj[MAXN];
map<string, int> ord;
void calc_ord(int pos, int &i, string &cur){
if(pos == 5){
ord[cur] = i++;
return;
}
cur.push_back('0');
cur.push_back('0');
calc_ord(pos + 1, i, cur);
cur[cur.size() - 1] = '1';
calc_ord(pos + 1, i, cur);
cur[cur.size() - 1] = '0';
cur[cur.size() - 2] = '1';
calc_ord(pos + 1, i, cur);
cur.pop_back();
cur.pop_back();
}
void send_pai(int n){
for(int i=1; i<n; i++){
for(int j=0; j<10; j++){
if(pai[i] & (1 << j)){
encode_bit(1);
} else encode_bit(0);
}
}
}
void send_hub(int n, int h){
string ans;
for(int i=1; i<n; i++){
if(dist[h][i] < dist[h][pai[i]]){
ans.push_back('0');
ans.push_back('1');
} else if(dist[h][i] == dist[h][pai[i]]){
ans.push_back('0');
ans.push_back('0');
} else{
ans.push_back('1');
ans.push_back('0');
}
}
if((n - 1) % 5 != 0){
for(int i=0; i<(5 - (n - 1) % 5); i++){
ans.push_back('0');
ans.push_back('0');
}
}
for(int i=0; i<ans.size(); i+=10){
string cur;
for(int j=i; j<(i + 10); j++) cur.push_back(ans[j]);
for(int j=0; j<8; j++){
if(ord[cur] & (1 << j)){
encode_bit(1);
} else encode_bit(0);
}
}
}
void bfs(int h){
queue<int> q;
q.push(h);
dist[h][h] = 0;
marc[h][h] = 1;
pai[0] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[h][u]){
dist[h][u] = dist[h][v] + 1;
marc[h][u] = 1;
if(h == 0) pai[u] = v;
q.push(u);
}
}
}
}
void encode(int n, int h, int p, int *a, int *b){
int i = 0;
string cur = "";
calc_ord(0, i, cur);
for(int i=0; i<n; i++) adj[i].clear();
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
marc[i][j] = 0;
}
}
for(int i=0; i<p; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for(int i=0; i<h; i++) bfs(i);
for(int i=1; i<h; i++){
for(int j=0; j<10; j++){
if(dist[i][0] & (1 << j)){
encode_bit(1);
} else encode_bit(0);
}
}
send_pai(n);
for(int i=1; i<h; i++) send_hub(n, i);
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
const int MAXN = 1e3 + 10;
static int pai[MAXN];
static int dist[MAXN][MAXN], marc[MAXN][MAXN];
int dif[MAXN];
static vector<int> adj[MAXN];
map<int, string> str;
void calc_str(int pos, int &i, string &cur){
if(pos == 5){
str[i++] = cur;
return;
}
cur.push_back('0');
cur.push_back('0');
calc_str(pos + 1, i, cur);
cur[cur.size() - 1] = '1';
calc_str(pos + 1, i, cur);
cur[cur.size() - 1] = '0';
cur[cur.size() - 2] = '1';
calc_str(pos + 1, i, cur);
cur.pop_back();
cur.pop_back();
}
void find_pai(int n){
for(int i=1; i<n; i++){
pai[i] = 0;
for(int j=0; j<10; j++){
pai[i] += decode_bit() * (1 << j);
}
}
}
void find_hub(int n, int h){
for(int i=1; i<n; i+=5){
int x = 0;
for(int j=0; j<8; j++) x += decode_bit() * (1 << j);
int j = 0, id = i;
while(id < min(n, i + 5)){
if(str[x][j] == '0'){
if(str[x][j + 1] == '0'){
dif[id] = 0;
} else dif[id] = -1;
} else dif[id] = 1;
j += 2;
id ++;
}
}
queue<int> q;
q.push(0);
marc[h][0] = 1;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[h][u]){
marc[h][u] = 1;
dist[h][u] = dist[h][v] + dif[u];
q.push(u);
}
}
}
}
void decode(int n, int h){
int i = 0;
string cur = "";
calc_str(0, i, cur);
for(int i=1; i<h; i++){
for(int j=0; j<10; j++){
dist[i][0] += decode_bit() * (1 << j);
}
}
find_pai(n);
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
marc[i][j] = 0;
}
}
for(int i=0; i<n; i++) adj[i].clear();
for(int i=1; i<n; i++){
adj[pai[i]].push_back(i);
adj[i].push_back(pai[i]);
}
queue<int> q;
for(int i=0; i<n; i++) dif[i] = 1;
q.push(0);
marc[0][0] = 1;
dist[0][0] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[0][u]){
marc[0][u] = 1;
dist[0][u] = dist[0][v] + dif[u];
q.push(u);
}
}
}
for(int i=1; i<h; i++) find_hub(n, i);
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
hops(i, j, dist[i][j]);
}
}
}
