#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int B = 7;
const int C = 1429;
vector<int> graf1[10010], graf2[10010];
int preorder[10010]; int preit;
int legenda[30010];
int nr=0, nr2=0;
int id[10010];
int r[10010];
void dfs1(int x, int o){
preorder[preit++] = x;
r[x]=1;
for(auto j: graf1[x])
if(j!=o)
dfs1(j, x);
if(r[x]<B){
if(o!=-1){
r[o]+=r[x];
graf2[o].push_back(x);
graf2[x].push_back(o);
}
}
}
bool odw[10010];
void dfs2(int x){
id[x] = nr*2*B+nr2++;
legenda[id[x]] = x;
odw[x] = 1;
for(auto j: graf2[x])
if(!odw[j])
dfs2(j);
}
string drzewko;
void dfs3(int x, int o){
for(auto j: graf2[x])
if(j!=o){
drzewko+='0';
dfs3(j,x);
drzewko+='1';
}
}
int odleglosci[30010][3];
int najblizej[3];
int n;
void dfs4(int x, int o, int szukany, int nro){
if(o==-1)
odleglosci[x][nro] = 0;
else
odleglosci[x][nro] = odleglosci[o][nro]+1;
if(id[x]/(2*B)==szukany)
najblizej[nro] = min(najblizej[nro], odleglosci[x][nro]);
for(auto j: graf1[x])
if(j!=o)
dfs4(j, x, szukany, nro);
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
int i;
n = N;
for(i=0;i<3*N;i++){
legenda[i] = -1;
odleglosci[i][0] = 0;
odleglosci[i][1] = 0;
odleglosci[i][2] = 0;
}
drzewko.clear();
preit = 0;
nr = 0;
nr2 = 0;
for(i=0;i<n;i++){
graf1[i].clear();
graf2[i].clear();
odw[i] = 0;
preorder[i] = 0;
id[i] = 0;
r[i] = 0;
}
for(i=0;i<N-1;i++){
graf1[U[i]].push_back(V[i]);
graf1[V[i]].push_back(U[i]);
}
dfs1(0,-1);
for(i=0;i<N;i++)
if(!odw[preorder[i]]){
nr2=0;
dfs2(preorder[i]);
nr++;
}
for(i=0;i<N;i++)
SetID(i, id[i]);
}
std::string SendA(std::string S) {
//cout<<"otzyamalam string: "<<S<<"\n";
int liczba = 0, i;
for(i=0;i<20;i++)
if(S[i]=='1')
liczba+=(1<<i);
int u = 0, v;
int suma = 0;
for(i=1;;i++){
if(suma+i<=liczba)
suma+=i;
else
break;
}
u = i-1;
v = liczba-suma;
//printf("odczytalam : u = %d, v = %d\n", u, v);
if(u==v){
dfs3(legenda[u*2*B], -1);
return drzewko;
}
najblizej[0]=1000000;
dfs4(legenda[u*2*B], -1, v, 0);
int pv=-2137, pu=legenda[u*2*B];
for(i=0;i<n;i++)
if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
pv = i;
break;
}
najblizej[1]=1000000;
dfs4(pv, -1, u, 1);
string out;
for(i=0;i<14;i++)
out+='0'+((najblizej[2]>>i)&1);
for(i=0;i<13;i++){
if(legenda[u*2*B+i]==-1)
out+="0000";
else{
int pom = odleglosci[legenda[u*2*B+i]][1]-najblizej[1];
for(int j=0;j<4;j++)
out+='0'+((pom>>j)&1);
}
}
for(i=0;i<13;i++){
if(legenda[v*2*B+i]==-1)
out+="0000";
else{
int pom = odleglosci[legenda[v*2*B+i]][0]-najblizej[0];
for(int j=0;j<4;j++)
out+='0'+((pom>>j)&1);
}
}
//for(i=0;i<28;i++)
// printf("Legenda[%d] = %d\n", i, legenda[i]);
//printf("pv = %d pu = %d\n", pv, pu);
return out;
}
#include "Benjamin.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int B = 7;
int x,y;
std::string SendB(int N, int X, int Y) {
//printf("Benjamin: X=%d Y=%d\n", X, Y);
int i;
if(X>Y)swap(X,Y);//X<Y
x = X;
y = Y;
int u, v;
v = X/(2*B);
u = Y/(2*B);
int suma=0;
for(i=0;i<=u;i++)
suma+=i;
suma+=v;
string out;
for(i=0;i<20;i++)
out+='0'+((suma>>i)&1);
//cout<<out;exit(0);
return out;
}
vector<int>graf[20];
int odl[20];
void dfs(int x, int o){
if(o>-1)
odl[x] = odl[o]+1;
for(auto j: graf[x])
if(j!=o)
dfs(j, x);
}
int Answer(std::string T) {
int u, v, i;
for(i=0;i<20;i++){
graf[i].clear();
odl[i] = 0;
}
v = x/(2*B);
u = y/(2*B);
if(u==v){
stack<int>stos;
stos.push(0);
int it=1;
for(auto j:T){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
}
dfs(x%(2*B), -1);
return odl[y%(2*B)];
}
int wynik = 0;
int pom=0;
for(i=0;i<14;i++)
if(T[i]=='1')
pom+=(1<<i);
wynik = pom;
//printf("odlegloc miedzy grupami= %d\n", pom);
pom = 0;
for(i=0;i<4;i++){
if(T[14+y%(2*B)*4+i]=='1')
pom+=(1<<i);
}
wynik+=pom;
//printf("odlegloc w u = %d\n", pom);
pom = 0;
for(i=0;i<4;i++){
if(T[14+13*4+x%(2*B)*4+i]=='1')
pom+=(1<<i);
}
wynik+=pom;
//printf("odlegloc w v = %d\n", pom);
//printf("odlegloc = %d\n", wynik);
//cout<<T<<"\n";
return wynik;
}
