#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int n, h, m;
vector<int> link[1002];
int par[1002];
bool visited[1002];
int dist[50][1002];
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
n = nv, h = nh, m = ne;
for(int i=0; i<m; i++){
link[v1[i]].push_back(v2[i]);
link[v2[i]].push_back(v1[i]);
}
/// BFS 트리를 인코딩
queue<int> que;
que.push(0), visited[0] = 1;
while(!que.empty()){
int x = que.front(); que.pop();
for(int y: link[x]){
if(visited[y]) continue;
visited[y] = 1, par[y] = x;
que.push(y);
}
}
for(int i=1; i<n; i++) for(int j=0; j<10; j++) encode_bit((par[i]>>j)&1);
/// 거리 차이를 인코딩
for(int s=0; s<h; s++){
fill(visited, visited+n+1, 0);
que.push(s), visited[s] = 1, dist[s][s] = 0;
while(!que.empty()){
int x = que.front(); que.pop();
for(int y: link[x]){
if(visited[y]) continue;
visited[y] = 1, dist[s][y] = dist[s][x] + 1;
que.push(y);
}
}
/// dist[s][0] 인코딩
for(int i=0; i<10; i++) encode_bit((dist[s][0]>>i)&1);
/// 나머지 거리 인코딩
vector<int> vec;
for(int i=1; i<n; i++){
int v = dist[s][i] - dist[s][par[i]] + 1;
vec.push_back(v);
if((int)vec.size() == 5){
int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
for(int d=0; d<8; d++) encode_bit((val>>d)&1);
vec.clear();
}
}
if(!vec.empty()){
vec.resize(5);
int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
for(int d=0; d<8; d++) encode_bit((val>>d)&1);
vec.clear();
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int n, h;
vector<int> link[1002];
int par[1002];
int offset[50][1002];
int dist[50][1002];
void dfs(int x){
for(int y: link[x]){
for(int s=0; s<h; s++) dist[s][y] = dist[s][x] + offset[s][y];
dfs(y);
}
}
}
void decode(int nv, int nh){
n = nv, h = nh;
for(int i=1; i<n; i++){
int v = 0;
for(int d=0; d<10; d++) v += decode_bit() << d;
par[i] = v;
link[v].push_back(i);
}
for(int s=0; s<h; s++){
for(int d=0; d<10; d++) dist[s][0] += decode_bit() << d;
for(int l=1; l<n; l+=5){
int v = 0;
for(int d=0; d<8; d++) v += decode_bit() << d;
for(int x=l; x<l+5 && x<n; x++){
offset[s][x] = v % 3 - 1;
v /= 3;
}
}
}
dfs(0);
for(int s=0; s<h; s++){
for(int i=0; i<n; i++){
hops(s, i, dist[s][i]);
}
}
}
