#include "Ali.h" #include <string> #include <vector> #include <set> #include <iostream> #include <cassert> using namespace std; #define pb push_back namespace { const int THR=16; const int MXG=1000; const int B=22; const int N=10050; const int L=15; int gid; int idx[N]; string enc[N]; vector<int> nodes[N]; int sz[N]; set<pair<int,int>> bad; vector<int> E[N]; int group[N],myIdx[N]; int par[N][L],dep[N]; } void DFSEZ(int u,int p){ par[u][0]=p; dep[u]=dep[p]+1; for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1]; for(int v:E[u]){ if(v!=p){ DFSEZ(v,u); } } } int LCA(int u,int v){ if(dep[u]<dep[v])swap(u,v); for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i]; for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i]; return u==v?v:par[v][0]; } int DIST(int u,int v){ return dep[u]+dep[v]-2*dep[LCA(u,v)]; } void DFS(int u,int p){ sz[u]=1; for(int v:E[u]){ if(v==p)continue; if(bad.count({u,v}))continue; DFS(v,u); sz[u]+=sz[v]; } } pair<int,int> Find(int u,int p,int n){ for(int v:E[u]){ if(v==p)continue; if(bad.count({u,v}))continue; if(sz[v]*3>=n-1 && (n-sz[v])*3>=n-1){ return {u,v}; } auto tmp=Find(v,u,n); if(tmp.first!=-1)return tmp; } return {-1,-1}; } void Mark(int u,int p,int g){ group[u]=g; myIdx[u]=idx[g]++; nodes[g].pb(u); //printf("%i ",u); for(int v:E[u]){ if(v==p)continue; if(bad.count({u,v}))continue; enc[g]+='1'; Mark(v,u,g); enc[g]+='0'; } } void Centroid(int u){ DFS(u,u); if(sz[u]<=THR){ //printf("Group(%i) => ",gid); Mark(u,u,gid); gid++; //printf("\n"); }else{ pair<int,int> edg=Find(u,u,sz[u]); assert(edg.first!=-1); bad.insert(edg); bad.insert({edg.second,edg.first}); Centroid(edg.first); Centroid(edg.second); } } void Init(int N, std::vector<int> U, std::vector<int> V) { for(int i=0;i<N;i++){ for(int j=0;j<L;j++){ par[i][j]=0; } dep[i]=0; E[i].clear(); gid=0; idx[i]=0; group[i]=0; myIdx[i]=0; nodes[i].clear(); enc[i]=""; } bad.clear(); for(int i=0;i<N-1;i++){ E[U[i]].pb(V[i]); E[V[i]].pb(U[i]); } DFSEZ(0,0); Centroid(0); for(int i=0;i<N;i++){ SetID(i,group[i]*THR+myIdx[i]); } } std::string SendA(std::string S) { int val=0; for(int i=0;i<20;i++){ val=val*2; if(S[i]=='1')val++; } int GX=val/MXG; int GY=val%MXG; int dist=0; int IX=0; int IY=0; if(GX!=GY){ dist=N*2; int ii=0; for(int i:nodes[GX]){ int jj=0; for(int j:nodes[GY]){ int d=DIST(i,j); if(dist>d){ dist=d; IX=ii; IY=jj; } jj++; } ii++; } } int num=dist*THR*THR+IX*THR+IY; string ans=""; for(int i=B-1;i>=0;i--){ if(num>>i&1)ans+="1"; else ans+="0"; } ans+=enc[GX]+"0"+enc[GY]; //cout << ans << endl; return ans; }

#include "Benjamin.h" #include <string> #include <vector> #include <stack> #include <cassert> using namespace std; namespace { const int THR=16; const int MXG=1000; const int B=22; int GX,GY,UX,UY,n; vector<int> E[THR]; int par[THR],dep[THR]; } int Rec(string T,int ptr){ //printf("REC\n"); for(int i=0;i<THR;i++){ E[i].clear(); par[i]=0; dep[i]=0; } stack<int> now; now.push(0); int idx=0; while(ptr<T.size()){ if(T[ptr]=='1'){ idx++; par[idx]=now.top(); //printf("%i -> %i\n",par[idx],idx); dep[idx]=dep[now.top()]+1; now.push(idx); }else{ now.pop(); if(now.empty()){ return ptr; } } ptr++; } return ptr; } int Dist(int u,int v){ //printf("DIST %i %i\n",u,v); if(dep[u]<dep[v])swap(u,v); int ans=0; while(dep[u]>dep[v]){ u=par[u]; ans++; } while(u!=v){ u=par[u]; v=par[v]; ans+=2; } return ans; } std::string SendB(int N, int X, int Y) { n=N; GX=X/THR; GY=Y/THR; UX=X%THR; UY=Y%THR; //printf("X: (%i, %i) Y: (%i, %i)\n",GX,UX,GY,UY); int val=GX*MXG+GY; assert(val<1000000); string ans=""; for(int i=19;i>=0;i--){ if(val>>i&1)ans+="1"; else ans+="0"; } return ans; } int Answer(std::string T) { int num=0; for(int i=0;i<B;i++){ num*=2; if(T[i]=='1')num++; } int dist=num/THR/THR; int IX=(num/THR)%THR; int IY=num%THR; int ptr=Rec(T,B); int ans=0; if(GX==GY){ ans=Dist(UX,UY); }else{ ans=dist+Dist(IX,UX); Rec(T,ptr+1); ans+=Dist(IY,UY); } return ans; }