#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
vector<int> t;
vector<bool> used;
int n;
void bfs(int node, vector<int> &dist)
{
dist.resize(n, 1e9);
dist[node] = 0;
queue<int> q;
q.push(node);
while(q.size())
{
int node = q.front();
q.pop();
for(auto it : v[node])
if(dist[node] + 1 < dist[it])
{
dist[it] = dist[node] + 1;
q.push(it);
}
}
}
void dfs(int node)
{
used[node] = 1;
for(auto it : v[node])
if(!used[it])
{
t[it] = node;
dfs(it);
}
}
void print(int x)
{
if(x == 0) encode_bit(0);
else if(x == 1) encode_bit(1), encode_bit(0);
else if(x == 2) encode_bit(1), encode_bit(1);
else assert(0);
}
void encode(int N, int H, int P, int *v1, int *v2)
{
vector<vector<int>> dist(H);
n = N;
v.resize(n);
int i, j;
for(i=0; i<P; ++i)
{
v[v1[i]].push_back(v2[i]);
v[v2[i]].push_back(v1[i]);
}
for(i=0; i<H; ++i)
bfs(i, dist[i]);
used.resize(n, 0);
t.resize(n);
dfs(0);
for(i=1; i<n; ++i)
{
int b = 10;
while(b--)
encode_bit((t[i] >> b) & 1);
}
for(i=0; i<H; ++i)
for(j=9; j>=0; --j)
encode_bit((dist[i][0]>>j) & 1);
vector<vector<int>> tip(n);
for(auto &it : tip) it.resize(H);
map<int, int> cnt;
for(i=1; i<n; ++i)
for(j=0; j<H; ++j)
{
tip[i][j] = dist[j][i] - dist[j][t[i]];
++cnt[tip[i][j]];
}
if(cnt[-1] >= cnt[0] && cnt[-1] >= cnt[1]) cnt[-1] = 0, cnt[0] = 1, cnt[1] = 2;
else if(cnt[0] >= cnt[-1] && cnt[0] >= cnt[1]) cnt[0] = 0, cnt[-1] = 1, cnt[1] = 2;
else cnt[1] = 0, cnt[0] = 1, cnt[-1] = 2;
print(cnt[-1]);
print(cnt[0]);
print(cnt[1]);
for(i=1; i<n; ++i)
for(j=0; j<H; ++j)
print(cnt[tip[i][j]]);
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
void read(int &x)
{
if(decode_bit() == 0) x = 0;
else if(decode_bit() == 0) x = 1;
else x = 2;
}
void decode(int n, int h)
{
int i, j;
vector<bool> marked(n, 0);
vector<int> t(n);
for(i=1; i<n; ++i)
{
int b = 10;
int x = 0;
while(b--)
x = x * 2 + decode_bit();
t[i] = x;
}
vector<vector<int>> dist(h);
for(auto &it : dist) it.resize(n);
for(i=0; i<h; ++i)
{
int x = 0;
for(j=0; j<10; ++j)
x = x * 2 + decode_bit();
dist[i][0] = x;
}
map<int, int> cnt;
read(cnt[-1]);
read(cnt[0]);
read(cnt[1]);
for(i=1; i<n; ++i)
for(j=0; j<h; ++j)
{
int x;
read(x);
for(int k=-1; k<=1; ++k)
if(cnt[k] == x)
dist[j][i] = dist[j][t[i]] + k;
}
for(i=0; i<n; ++i)
for(j=0; j<h; ++j)
hops(j, i, dist[j][i]);
}
