#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; //mt19937 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[20]; map<string,int> tree_map; void gen_trees() { rep2(i,0,19) trees[i] = {}; trees[0].pb(""); rep2(i,1,19) { rep2(k,0,i) { if(k > i-1-k || k >= 10 || i-1-k >= 10) 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[19])) tree_map[trees[19][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) >= 10) { 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+")"; } // cout << v << " p: "; // forall(it,p) cout << it << " "; // cout << " dfa_hash\n"; graph2[v] = p; return ans; } int cur_ind; void dfs_inds(int v, int pop) { // cout << v << " " << cur_ind << " dfs_ind\n"; vert_ind[v] = cur_ind++; forall(it,graph2[v]) dfs_inds(it,v); } void set_inds(vi x, int c) { // forall(it,x) cout << it << ' '; // cout << " comp\n"; 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) < 19) { int pop = r; int r2 = r; while(true) { int nxt = -1; forall(it,graph2[r2]) { if(it != pop && dfs_sub(it,r2) < 9) 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*19; dfs_inds(r,r); // forall(it,x) cout << vert_ind[it] << " "; // cout << " inds\n"; 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}); } } } 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]); // rep(i,n) cout << vert_ind[i] << " "; // cout << " vert\n"; //cout << vert_ind[5883] << " " << vert_ind[4764] << " inds\n"; } string SendA(string S) { string ans; int x = 0; int y = 0; rep(i,10) if(S[i] == '1') x += (1<<i); rep2(i,10,19) if(S[i] == '1') y += (1<<(i-10)); //cout << x << " " << y << " " << comp_tree[x] << " "<< comp_tree[y]<< " xy\n"; if(x == y) { rep(i,14) { if(comp_tree[x]&(1<<i)) ans += "1"; else ans += "0"; } return ans; } rep(i,14) { if(comp_tree[x]&(1<<i)) ans += "1"; else ans += "0"; } rep(i,14) { if(comp_tree[y]&(1<<i)) ans += "1"; else ans += "0"; } bfs(comps[x][0]); pii best = {1e9,1e9}; forall(it,comps[y]) best = min(best,{dist[it],it}); rep(i,15) if(best.ff&(1<<i)) ans += "1"; else ans += "0"; rep(i,5) if((vert_ind[best.ss]%19)&(1<<i)) ans += "1"; else ans += "0"; return ans; }

#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; //mt19937 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[20]; map<string,int> tree_map; void gen_trees() { rep2(i,0,19) trees[i] = {}; trees[0].pb(""); rep2(i,1,19) { rep2(k,0,i) { if(k > i-1-k || k >= 10 || i-1-k >= 10) 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[19])) tree_map[trees[19][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}); } } } string SendB(int N, int X, int Y) { n = N; x = X; y = Y; // /cout << x << " " << y << " inds2\n"; if(x > y) swap(x,y); string ans; rep(i,10) if((x/19)&(1<<i)) ans += "1"; else ans += "0"; rep(i,10) if((y/19)&(1<<i)) ans += "1"; else ans += "0"; // cout << ans << " sendB\n"; return ans; } int Answer(string T) { int indx = 0; int indy = 0; int d = 0; int b = 0; rep(i,14) if(T[i] == '1') indx += (1<<i); if(siz(T) > 14) { rep2(i,14,27) if(T[i] == '1') indy += (1<<(i-14)); rep2(i,28,42) if(T[i] == '1') d += (1<<(i-28)); rep2(i,43,47) if(T[i] == '1') b += (1<<(i-43)); } // cout << indx << " " << indy << " " << d << " " << b << " info\n"; x %= 19; y %= 19; rep(i,50) graph[i] = {}; cur_ind = 0; gen_trees(); gen_tree(trees[19][indx]); pii s = {y,0}; if(siz(T) > 14) { gen_tree(trees[19][indy]); bfs(y+19); s = {0,d+dist[b+19]}; } bfs(s.ff); return dist[x]+s.ss; }