#include "Encoder.h" #include <bits/stdc++.h> using namespace std; #define sp << " " << #define emb emplace_back #define inf 1000000 #define MAXN 250000 typedef pair<int,int> ii; const int D=11; int cnt,dp[MAXN+5][D+1]; vector<int> g[MAXN+5],gb[2*MAXN+5]; int L[MAXN+5],R[MAXN+5],VAL[MAXN+5],num=-1; void initBT(int x,int par){ for(int i=0;i<(int)g[x].size();i++){ if(g[x][i]==par){ g[x].erase(g[x].begin()+i); break; } } int cn=g[x].size(); if(cn>2){ vector<int> bt(2*cn); int l=cn,r=2*cn; for(int i=l;i<r;i++) bt[i]=g[x][i-cn]; l>>=1;r>>=1; while(l>0){ for(int i=r-1;i>=l;i--){ bt[i]=(i>1?cnt++:x); gb[bt[i]].emb(bt[2*i]); gb[bt[i]].emb(bt[2*i+1]); } l>>=1;r>>=1; } } else{ for(auto i:g[x]) gb[x].emb(i); } for(auto i:g[x]) initBT(i,x); } void dfs(int x){ for(auto i:gb[x]) dfs(i); for(int i=0;i<=D;i++) dp[x][i]=inf; if(gb[x].empty()) dp[x][0]=dp[x][1]=1; else if(gb[x].size()==1){ int child=gb[x][0]; for(int j=1;j<=D;j++){ dp[x][j]=dp[child][j-1]+(j==1); dp[x][0]=min(dp[x][0],dp[x][j]); } } else{ int c1=gb[x][0],c2=gb[x][1]; for(int i=0;i<=D;i++) for(int j=0;j<=D;j++) dp[x][max(i,j)+1]=min(dp[x][max(i,j)+1],dp[c1][i]+dp[c2][j]+1-(i>0)-(j>0)); for(int i=1;i<=D;i++) dp[x][0]=min(dp[x][0],dp[x][i]); } } void calc(int x,int k){ if(k==0){ for(k=1;k<=D && dp[x][k]!=dp[x][0];k++); VAL[x]=1; num++; } L[x]=num; if(gb[x].empty()); else if(gb[x].size()==1){ int child=gb[x][0]; VAL[child]=VAL[x]<<1; calc(child,k-1); } else{ int c1=gb[x][0],c2=gb[x][1]; VAL[c1]=VAL[x]<<1; VAL[c2]=VAL[x]<<1|1; int k1,k2,ff=0; for(int i=0;i<=D && !ff;i++){ for(int j=0;j<=D && !ff;j++){ if(max(i,j)+1!=k) continue; if(dp[c1][i]+dp[c2][j]+1-(i>0)-(j>0)==dp[x][k]) k1=i,k2=j,ff=1; } } calc(c1,k1);calc(c2,k2); } R[x]=num; } void Encode(int N, int A[], int B[]) { for(int i=0;i<N-1;i++){ g[A[i]].emb(B[i]); g[B[i]].emb(A[i]); } cnt=N; initBT(0,-1); //~ for(int i=0;i<cnt;i++){ //~ cout << i << ": "; //~ for(auto j:gb[i]) //~ cout << j << " "; //~ cout << "\n"; //~ } dfs(0); //~ for(int i=0;i<cnt;i++){ //~ for(int j=0;j<=D;j++) //~ cout << dp[i][j] << " "; //~ cout << "\n"; //~ } calc(0,0); for(int i=0;i<N;i++){ //~ cout << L[i] sp R[i] sp VAL[i] << "\n"; long long code=VAL[i]+((long long)R[i]<<11)+((long long)L[i]<<30); Code(i,code); } }

#include "Device.h" #include <bits/stdc++.h> using namespace std; const int d=11,seg=19; void InitDevice(){} int Answer(long long S, long long T){ int val1=S%(1LL<<d); int r1=(S>>d)%(1LL<<seg); int l1=(S>>seg+d); int val2=T%(1LL<<d); int r2=(T>>d)%(1LL<<seg); int l2=(T>>seg+d); if(l1==l2){ if(val1<val2){ while(val1<val2) val2>>=1; if(val1==val2) return 1; return 2; } else{ while(val2<val1) val1>>=1; if(val1==val2) return 0; return 2; } } else{ if(l1<=l2 && r2<=r1) return 1; if(l2<=l1 && r1<=r2) return 0; return 2; } }