#include "Ali.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; namespace { vector<string> trees[16]; map<string,int> tree_map; void gen_trees() { rep2(i,0,13) trees[i] = {}; trees[0].pb(""); rep2(i,1,13) { rep2(k,0,i) { if(k > i-1-k || k >= 7 || i-1-k >= 7) continue; forall(it,trees[k]) { forall(it2,trees[i-1-k]) { if(it < it2) trees[i].pb("("+it+it2+")"); else trees[i].pb("("+it2+it+")"); } } } } rep(i,siz(trees[13])) tree_map[trees[13][i]] = i; } vi graph[130001]; vi graph2[130001]; bool is_in[130001]; vector<vi> comps; map<int,int> vert_ind; int comp_tree[100001]; int n; vi dfs_comps(int v, int pop) { vi cur = {v}; forall(it,graph[v]) { if(it != pop) { vi v2 = dfs_comps(it,v); forall(it2,v2) cur.pb(it2); } } if(siz(cur) >= 7) { comps.pb(cur); cur = {}; } return cur; } int dfs_sub(int v, int pop) { int s = 1; forall(it,graph2[v]) if(it != pop) s += dfs_sub(it,v); return s; } string hash_tree(int v, int pop) { vi p; forall(it,graph2[v]) if(it != pop) p.pb(it); string ans; if(siz(p) == 0) ans = "()"; else if(siz(p) == 1) ans = "("+hash_tree(p[0],v)+")"; else { string s1 = hash_tree(p[0],v); string s2 = hash_tree(p[1],v); if(s2 < s1) { swap(s1,s2); swap(p[0],p[1]); } ans = "("+s1+s2+")"; } graph2[v] = p; return ans; } int cur_ind; void dfs_inds(int v, int pop) { vert_ind[v] = cur_ind++; forall(it,graph2[v]) dfs_inds(it,v); } void set_inds(vi x, int c) { forall(it,x) is_in[it] = 1; forall(it,x) { graph2[it] = {}; forall(it2,graph[it]) if(is_in[it2]) graph2[it].pb(it2); } int r = x[0]; int cur = n; rep2(i,n,n+20) graph2[i] = {}; while(siz(x) < 13) { int pop = r; int r2 = r; while(true) { int nxt = -1; forall(it,graph2[r2]) { if(it != pop && dfs_sub(it,r2) < 6) nxt = it; } if(nxt == -1) { graph2[r2].pb(cur); x.pb(cur); cur++; break; } else { pop = r2; r2 = nxt; } } } string h = hash_tree(r,r); comp_tree[c] = tree_map[h]; cur_ind = c*13; dfs_inds(r,r); forall(it,x) is_in[it] = 0; } int dist[100001]; void bfs(int v) { rep(i,n) dist[i] = 1e9; queue<pii> q; q.push({v,0}); while(!q.empty()) { pii t = q.front(); q.pop(); if(dist[t.ff] != 1e9) continue; dist[t.ff] = t.ss; forall(it,graph[t.ff]) q.push({it,t.ss+1}); } } const int k = 1447; pii pair_[k*k+1]; bool was = 0; void init2() { if(!was) { was = 1; int cur = 0; rep2(i,0,k-1) { rep2(j,i,k-1) { pair_[cur++] = {i,j}; } } } } pll segs[32]; } void Init(int N, vi U, vi V) { n = N; rep(i,n) graph[i] = {}; gen_trees(); rep(i,n-1) { graph[U[i]].pb(V[i]); graph[V[i]].pb(U[i]); } comps = {}; int r = 0; rep(i,n) if(siz(graph[i]) == 1) { r = i; break; } vi x = dfs_comps(r,r); if(siz(x) != 0) comps.pb(x); int c = 0; forall(it,comps) set_inds(it,c++); rep(i,n) SetID(i,vert_ind[i]); } string SendA(string S) { ll l = 0; ll r = 1; rep2(i,1,31) { if(i == 7) continue; segs[i] = {l,r}; ll len = (r-l+1)*2; l = r+1; r = l+len-1; } int x = 0; int y = 0; int ans3 = 0; rep(i,20) if(S[i] == '1') ans3 += (1<<i); init2(); x = pair_[ans3].ff; y = pair_[ans3].ss; if(x == y) { string ans; rep(i,7) { if(comp_tree[x]&(1<<i)) ans += "1"; else ans += "0"; } return ans; } ll ans = comp_tree[x]+comp_tree[y]*(ll)siz(trees[13]); bfs(comps[x][0]); pii best = {1e9,1e9}; forall(it,comps[y]) best = min(best,{dist[it],it}); ans += (ll)best.ff*(ll)siz(trees[13])*(ll)siz(trees[13]); ans += (ll)(vert_ind[best.ss]%13)*(ll)siz(trees[13])*(ll)siz(trees[13])*(ll)(n-1); string ans2; rep2(i,1,31) { if(i == 7) continue; if(segs[i].ff <= ans && ans <= segs[i].ss) { rep(j,i) { if((ans-segs[i].ff)&(1LL<<(ll)j)) ans2 += "1"; else ans2 += "0"; } } } return ans2; }

#include "Benjamin.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; namespace { vector<string> trees[16]; map<string,int> tree_map; void gen_trees() { rep2(i,0,13) trees[i] = {}; trees[0].pb(""); rep2(i,1,13) { rep2(k,0,i) { if(k > i-1-k || k >= 7 || i-1-k >= 7) continue; forall(it,trees[k]) { forall(it2,trees[i-1-k]) { if(it < it2) trees[i].pb("("+it+it2+")"); else trees[i].pb("("+it2+it+")"); } } } } rep(i,siz(trees[13])) tree_map[trees[13][i]] = i; } int n,x,y; vi graph[50]; int cur_ind; int gen_tree(string s) { int v = cur_ind++; if(s == "()") return v; string s1,s2; int c = 0; rep2(i,1,siz(s)-1) { if(s[i] == '(') c++; else c--; s1 += s[i]; if(c == 0) break; } rep2(i,siz(s1)+1,siz(s)-2) s2 += s[i]; if(siz(s1) > 0) { int v2 = gen_tree(s1); graph[v].pb(v2); graph[v2].pb(v); } if(siz(s2) > 0) { int v2 = gen_tree(s2); graph[v].pb(v2); graph[v2].pb(v); } return v; } int dist[50]; void bfs(int v) { rep(i,50) dist[i] = 1e9; queue<pii> q; q.push({v,0}); while(!q.empty()) { pii t = q.front(); q.pop(); if(dist[t.ff] != 1e9) continue; dist[t.ff] = t.ss; forall(it,graph[t.ff]) q.push({it,t.ss+1}); } } const int k = 1447; int ind[1447][1447]; bool was = 0; void init2() { if(!was) { was = 1; int cur = 0; rep2(i,0,k-1) { rep2(j,i,k-1) { ind[i][j] = cur++; } } } } pll segs[32]; } string SendB(int N, int X, int Y) { n = N; x = X; y = Y; if(x > y) swap(x,y); int x2 = x/13; int y2 = y/13; init2(); ll ans = ind[x2][y2]; string ans2; rep(i,20) if(ans&(1<<i)) ans2 += "1"; else ans2 += "0"; return ans2; } int Answer(string T) { ll l = 0; ll r = 1; rep2(i,1,31) { if(i == 7) continue; segs[i] = {l,r}; ll len = (r-l+1)*2; l = r+1; r = l+len-1; } //cout << r << " r\n"; int indx = 0; int indy = 0; int d = 0; int b = 0; gen_trees(); if(siz(T) != 7) { ll ans = segs[siz(T)].ff; rep(i,siz(T)) if(T[i] == '1') ans += (1<<i); indx = ans%siz(trees[13]); ans /= siz(trees[13]); indy = ans%siz(trees[13]); ans /= siz(trees[13]); d = ans%(n-1); ans /= (n-1); b = ans; } else rep(i,7) if(T[i] == '1') indx += (1<<i); x %= 13; y %= 13; rep(i,50) graph[i] = {}; cur_ind = 0; gen_tree(trees[13][indx]); pii s = {y,0}; if(siz(T) != 7) { gen_tree(trees[13][indy]); bfs(y+13); s = {0,d+dist[b+13]}; } bfs(s.ff); return dist[x]+s.ss; }