#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;
int zlicz=0;
void dfs3(int x, int o){
//cout<<drzewko<<"\n";
//zlicz++;
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);
}
int dfs5(int x, int o){
int w = 1;
for(auto j: graf2[x])
if(j!=o)
w+=dfs5(j,x);
return w;
}
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(dfs5(i, -1)>13){
printf("ZA DUZA GRUPA\n");
exit(0);
}
}
for(i=0;i<N;i++)
if(!odw[preorder[i]]){
nr2=0;
dfs2(preorder[i]);
nr++;
}
/*
for(i=0;i<N;i++){
printf("%d: r=%d id=%d\n", i, r[i], id[i]);
}*/
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;
//u>=v
//printf("odczytalam : u = %d, v = %d\n", u, v);
if(u==v){
//zlicz = 0;
drzewko="";
dfs3(legenda[u*2*B], -1);
//cout<<drzewko<<"\n"<<zlicz<<"\n";
return drzewko;
}
najblizej[0]=1000000;
dfs4(legenda[u*2*B], -1, v, 0);
int pv=-2137, pu=-2137;
for(i=0;i<n;i++)
if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
pv = i;
break;
}
string out;
for(i=0;i<14;i++)
out+='0'+((najblizej[0]>>i)&1);
for(i=0;i<4;i++)
out+='0'+(((id[pv]%(2*B))>>i)&1);
drzewko="";
//dodaj drzewko v
dfs3(legenda[v*2*B], -1);
/*
if(dfs5(legenda[v*2*B], -1)>13){
printf("ZA DUZA GRUPA");
exit(0);
}*/
while(drzewko.size()<24)drzewko+='1';
/*
if(drzewko.size()>32){
printf("ZA DUZE DRZEWKO");
exit(0);
}*/
for(i=0;i<24;i++)
out+=drzewko[i];
// out=out+drzewko;
drzewko="";
//dodaj drzewko u
dfs3(legenda[u*2*B], -1);
/*
if(dfs5(legenda[u*2*B], -1)>13){
printf("ZA DUZA GRUPA");
exit(0);
}*/
while(drzewko.size()<24)drzewko+='1';
/*
if(drzewko.size()>32){
printf("ZA DUZE DRZEWKO");
exit(0);
}*/
for(i=0;i<24;i++)
out+=drzewko[i];
//out+=drzewko;
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();
}
odl[x%(2*B)]=0;
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);
int pv = 0;
for(i=0;i<4;i++)
if(T[i+14]=='1')
pv+=1<<i;
//printf("pv = %d\n", pv);
stack<int>stos;
string drzewko = T.substr(14+4, 24);
stos.push(0);
int it=1;
for(auto j:drzewko){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
if(stos.size()==0)break;
}
odl[pv] = 0;
dfs(pv, -1);
wynik += odl[x%(2*B)];
//printf("odleglosc w v = %d\n", odl[x%(2*B)]);
drzewko= T.substr(14+4+24, 24);
while(stos.size())stos.pop();
stos.push(0);
for(i=0;i<20;i++){
graf[i].clear();
odl[i] = 0;
}
it=1;
for(auto j:drzewko){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
if(stos.size()==0)break;
}
odl[0] = 0;
dfs(0, -1);
wynik += odl[y%(2*B)];
//printf("odleglosc w u = %d, y = %d\n", odl[y%(2*B)], y%(2*B));
//cout<<drzewko<<"\n";
//cout<<T<<"\n";
//cout<<T.substr(14+4+24, 24)<<"\n";
return wynik;
}
//10000000000000 0100 001111111111111111111111 000000111111111111111111
