Advertisement
Guest User

Untitled

a guest
Aug 17th, 2022
1,407
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. vector<vector<int>>v;
  6. int n;
  7. vector<vector<int>>up(100005,vector<int>(21,-1)),Xor(100005,vector<int>(21)),And(100005,vector<int>(21)),Or(100005,vector<int>(21));
  8. map<pair<int,int>,int>weight;
  9. vector<int>lvl(100005);
  10.  
  11. void binary_lifting(int node,int par)
  12. {
  13.     up[node][0] = par;
  14.     Xor[node][0] = weight[{node,par}];
  15.     And[node][0] = weight[{node,par}];
  16.     Or[node][0] = weight[{node,par}];
  17.    
  18.     for(int i=1;i<21;i++)
  19.     {
  20.         if(up[node][i-1]!=-1)
  21.         {
  22.             up[node][i] = up[up[node][i-1]][i-1];
  23.             Xor[node][i] = Xor[up[node][i-1]][i-1]^Xor[node][i-1];
  24.             And[node][i] = And[up[node][i-1]][i-1]&And[node][i-1];
  25.             Or[node][i] = Or[up[node][i-1]][i-1]|Or[node][i-1];
  26.         }else
  27.         {
  28.             up[node][i] = -1;
  29.         }
  30.        
  31.     }
  32.    
  33.    
  34.     for(auto &x:v[node])
  35.     {
  36.         if(x!=par)
  37.         {
  38.             binary_lifting(x, node);
  39.         }
  40.     }
  41. }
  42.  
  43. int liftnode(int a,int jump)
  44. {
  45.     for(int i=20;i>=0;i--)
  46.     {
  47.         if(jump == 0 || a==-1)return a;
  48.        
  49.         if(jump >= (1 << i))
  50.         {
  51.             a = up[a][i];
  52.             jump -= (1 << i);
  53.         }
  54.     }
  55.     return a;
  56. }
  57.  
  58. int lca(int a,int b)
  59. {
  60.     int x1=0,y1=~0,z1=0,x2=0,y2=~0,z2=0;
  61.     // xor and or
  62.    
  63.     if(lvl[a] > lvl[b])swap(a,b);
  64.     int st=a,en=b;
  65.    
  66.     int dif = lvl[b] - lvl[a];
  67.     b = liftnode(b,dif);
  68.    
  69.     int jump = dif;
  70.     for(int i=20;i>=0;i--)
  71.     {
  72.         if(jump == 0)break;
  73.        
  74.         if(jump >= (1 << i))
  75.         {
  76.  
  77.             // x1 ^= Xor[en][i];   WRONG BCOZ OF THESE 3 LINES
  78.             // y1 &= And[en][i];    F*********************CK !!!   
  79.             // z1 |= Or[en][i];
  80.  
  81.             x2 ^= Xor[en][i];
  82.             y2 &= And[en][i];
  83.             z2 |= Or[en][i];
  84.            
  85.             en = up[en][i];
  86.             jump -= (1 << i);
  87.         }
  88.     }
  89.    
  90.     if(a==b)return x2+y2+z2;
  91.    
  92.     for(int i=20;i>=0;i--)
  93.     {
  94.         int jump = (1 << i);
  95.         if(liftnode(a, jump) != liftnode(b, jump) && liftnode(b, jump)!=-1)
  96.         {
  97.             x1 ^= Xor[a][i];
  98.             y1 &= And[a][i];
  99.             z1 |= Or[a][i];
  100.            
  101.             x2 ^= Xor[b][i];
  102.             y2 &= And[b][i];
  103.             z2 |= Or[b][i];
  104.            
  105.             a = up[a][i];
  106.             b = up[b][i];
  107.         }
  108.     }
  109.     int xx = a,yy = b;
  110.    
  111.     int lc = liftnode(a, 1);
  112.    
  113.     x1 ^= weight[{lc,xx}];
  114.     y1 &= weight[{lc,xx}];
  115.     z1 |= weight[{lc,xx}];
  116.    
  117.     x2 ^= weight[{lc,yy}];
  118.     y2 &= weight[{lc,yy}];
  119.     z2 |= weight[{lc,yy}];
  120.    
  121.     int ans = (x1^x2) + (y1&y2) + (z1|z2);
  122.    
  123.     return ans;
  124.    
  125.    
  126. }
  127.  
  128. void bfs()
  129. {
  130.     queue<int>q;
  131.     vector<int>vis(100005,0);
  132.     q.push(1);
  133.    
  134.     while(q.size())
  135.     {
  136.         int node = q.front();
  137.         q.pop();
  138.         vis[node]=1;
  139.         for(auto &x:v[node])
  140.         {
  141.             if(!vis[x])
  142.             {
  143.                 q.push(x);
  144.                 lvl[x] = lvl[node]+1;
  145.             }
  146.         }
  147.     }
  148. }
  149.  
  150. vector<int> getPathXORAND(int tree_nodes, vector<int> tree_from, vector<int> tree_to, vector<int> tree_weight, vector<vector<int>> queries) {
  151.     n = tree_nodes;
  152.     v.resize(n+1,vector<int>());
  153.    
  154.     int c = tree_from.size();
  155.     for(int i=0;i<c;i++)
  156.     {
  157.         v[tree_from[i]].push_back(tree_to[i]);
  158.         v[tree_to[i]].push_back(tree_from[i]);
  159.         weight[{tree_from[i],tree_to[i]}] = tree_weight[i];
  160.         weight[{tree_to[i],tree_from[i]}] = tree_weight[i];
  161.     }
  162.     vector<int>res;
  163.    
  164.     bfs();
  165.    
  166.     binary_lifting(1,-1);
  167.    
  168.     c=queries.size();
  169.    
  170.     for(int i=0;i<c;i++)
  171.     {
  172.         int a = queries[i][0], b = queries[i][1];
  173.        
  174.         if(a!=b)res.push_back(lca(a,b));
  175.         else res.push_back(0);
  176.     }
  177.    
  178.     up.clear();
  179.     Xor.clear();
  180.     And.clear();
  181.     Or.clear();
  182.     lvl.clear();
  183.     weight.clear();
  184.    
  185.    
  186.     return res;
  187. }
  188.  
  189. int main()
  190. {
  191.     int nodes,paths;cin >> nodes >> paths;
  192.     vector<int>u(paths),v(paths),w(paths);
  193.     for(int i=0;i<paths;i++)
  194.     {
  195.         cin >> u[i];
  196.     }
  197.     for(int i=0;i<paths;i++)
  198.     {
  199.         cin >> v[i];
  200.     }
  201.     for(int i=0;i<paths;i++)
  202.     {
  203.         cin >> w[i];
  204.     }
  205.     int q;cin >> q;
  206.     vector<vector<int>>query(q);
  207.     for(int i=0;i<q;i++)
  208.     {
  209.         int a,b;cin>>a>>b;
  210.         query[i].push_back(a);
  211.         query[i].push_back(b);
  212.     }
  213.     vector<int>ans = getPathXORAND(nodes,u,v,w,query);
  214.  
  215.     for(auto &x:ans)cout <<x<<" ";
  216.  
  217.     return 0;
  218. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement