#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
uint a[SZ];
big_int() {
memset(a, 0, sizeof a);
}
void triple() {
for(int i = 0; i < SZ; i++) a[i] *= 3;
for(int i = 0; i+1 < SZ; i++) {
a[i+1] += a[i]>>30;
a[i] &= ful;
}
}
void add(uint x) {
int co = x;
for(int i = 0; co;) {
a[i] += co;
co = a[i]>>30;
a[i] &= ful;
}
}
friend big_int operator+(big_int x, const big_int &y) {
uint co = 0;
for(int i = 0; i < SZ; i++) {
x.a[i] += y.a[i]+co;
co = x.a[i]>>30;
x.a[i] &= ful;
}
return x;
}
friend bool operator<=(const big_int &a, const big_int &b) {
int pos = SZ-1;
while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
return pos == -1 || a.a[pos] <= b.a[pos];
}
void send() {
for(int i = 0; i < N; i++) {
int val = a[i/30];
val >>= i%30;
encode_bit(val&1);
}
}
void get() {
for(int i = 0; i < N; i++) {
int val = decode_bit();
val <<= i%30;
a[i/30] |= val;
}
}
void print() {
for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
}
};
int n, par[N];
vector<int> g[N];
template<int build_tree>
void bfs(int v) {
vector<int> dist(n+1, -1);
queue<int> q;
auto enq = [&](int v, int d, int P) {
if(dist[v] != -1) return;
dist[v] = d;
if(build_tree) par[v] = P;
q.push(v);
};
enq(v, 0, -1);
while(!q.empty()) {
int v = q.front();q.pop();
for(auto i : g[v]) enq(i, dist[v]+1, v);
}
//for(int i = 0; i < n; i++) cout << dist[i] << " "; cout << endl;
if(build_tree) {
for(int i = 1; i < n; i++)
for(int j = 0; j < 10; j++)
encode_bit((par[i]>>j)&1);
} else {
for(int i = 0; i < 10; i++) encode_bit((dist[0]>>i)&1);
big_int res;
for(int i = 1; i < n; i++) {
res.triple();
res.add(1 + dist[i] - dist[par[i]]);
//cout << v << " | " << i << " | " << 1 + dist[i] - dist[par[i]] << " res " << dist[i] << endl;
}
//cout << v << " res " << res.a[0] << endl;
res.send();
}
}
};
void encode(int V, int H, int E, int *v1, int *v2){
n = V;
for(int i = 0; i < E; i++) g[v1[i]].push_back(v2[i]);
for(int i = 0; i < E; i++) g[v2[i]].push_back(v1[i]);
bfs<1>(0);
for(int i = 1; i < H; i++) bfs<0>(i);
return;
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
uint a[SZ];
big_int() {
memset(a, 0, sizeof a);
}
void triple() {
for(int i = 0; i < SZ; i++) a[i] *= 3;
for(int i = 0; i+1 < SZ; i++) {
a[i+1] += a[i]>>30;
a[i] &= ful;
}
}
void add(uint x) {
int co = x;
for(int i = 0; co;) {
a[i] += co;
co = a[i]>>30;
a[i] &= ful;
}
}
friend big_int operator+(big_int x, const big_int &y) {
uint co = 0;
for(int i = 0; i < SZ; i++) {
x.a[i] += y.a[i]+co;
co = x.a[i]>>30;
x.a[i] &= ful;
}
return x;
}
friend bool operator<=(const big_int &a, const big_int &b) {
int pos = SZ-1;
while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
return pos == -1 || a.a[pos] <= b.a[pos];
}
void send() {
for(int i = 0; i < N; i++) {
int val = a[i/30];
val >>= i%30;
encode_bit(val&1);
}
}
void get() {
for(int i = 0; i < N; i++) {
int val = decode_bit();
val <<= i%30;
a[i/30] |= val;
}
}
void print() {
for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
}
};
int n, h, d21[N], par[N];
vector<int> g[N], ord;
void dfs(int v) {
ord.push_back(v);
for(int i : g[v]) dfs(i);
}
big_int pws[N];
}
void decode(int nv, int nh) {
n = nv;
h = nh;
d21[0] = 0;
for(int i = 1; i < n; i++) {
for(int j = 0; j < 10; j++) {
par[i] |= decode_bit()<<j;
}
g[par[i]].push_back(i);
}
dfs(0);
//cout << "pT2\n";
for(auto i : ord) if(i) d21[i] = d21[par[i]] + 1;
for(int i = 0; i < n; i++) hops(0, i, d21[i]);
pws[0].add(1);
for(int i = 1; i < n; i++) pws[i] = pws[i-1], pws[i].triple();
for(int hl = 1; hl < h; hl++) {
memset(d21, 0, sizeof d21);
for(int j = 0; j < 10; j++) d21[0] |= decode_bit()<<j;
big_int dif;
//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
dif.get();
//cout << hl << " == " << dif.a[0] << endl;
//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
big_int cur;
for(int i = 1; i < n; i++) {
int CCC = 0;
big_int &cp = pws[n-i-1], nxt;
//cout << cur.a[0] << " " << cp.a[0] << " " << dif.a[0] << endl;
while(nxt = cur+cp, nxt <= dif) {
cur = nxt;
//cout << "inc\n";
d21[i]++;
}
//cout << cur.a[0] << endl;
//cout << hl << " : " << i << " : " << d21[i] << endl;
}
for(auto i : ord) if(i) {
d21[i] -= 1;
d21[i] += d21[par[i]];
//cout << hl << " " << i << " res " << d21[i] << endl;
}
for(int i = 0; i < n; i++) hops(hl, i, d21[i]);
}
}
