fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long in;
  4. #define lcm(a,b) ((a*b)/__gcd(a,b))
  5. #define max(a,b) ((a)>(b)?(a):(b))
  6. #define vi vector<in>
  7. #define vvi vector<vector<in> >
  8. #define vpi vector<pair<in,in> >
  9. #define pb push_back
  10. #define mp make_pair
  11. #define pii pair<in,in>
  12. #define fi first
  13. #define se second
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  17.  
  18. const in maxn=200005;
  19. vector<in> adj[maxn];
  20. vector<in> val(maxn);
  21. vector<in> ar;
  22. vector<pii> tme(maxn,mp(0,0));
  23. vector<in> flag(maxn);
  24. struct trie
  25. {
  26.     trie* arr[2];
  27.     in minver,mst;//minimumVertex,maxStartTime
  28.     trie() {
  29.         arr[0]=arr[1]=NULL;
  30.         minver=maxn;
  31.         mst=0;
  32.     }
  33. };
  34. vector<trie*> ptries(2*maxn);
  35.  
  36. //persistent trie
  37. trie* insert(trie* root,in ver)
  38. {
  39.     trie* newroot=new trie();
  40.     trie* source=newroot;
  41.     in v=val[ver];
  42.     in st=tme[ver].fi;
  43.     trie* temp=root;
  44.     for(in i=19; i>=0; i--)
  45.     {
  46.         bool bit=v&(1<<i);
  47.         newroot->mst=max(newroot->mst,st);
  48.         if(temp!=NULL)
  49.         {
  50.             newroot->arr[!bit]=temp->arr[!bit];
  51.             temp=temp->arr[bit];
  52.         }
  53.         newroot->arr[bit]=new trie();
  54.         newroot=newroot->arr[bit];
  55.     }
  56.     newroot->mst=max(newroot->mst,st);
  57.     newroot->minver=min(newroot->minver,ver);
  58.     return source;
  59. }
  60. //euler tour
  61. void dfs(in i,in p)
  62. {
  63.     ar.pb(i);
  64.     for(in j:adj[i])
  65.         if(j!=p)
  66.             dfs(j,i);
  67.     ar.pb(i);
  68. }
  69.  
  70. pii querytrie(in ver,in k)
  71. {
  72.     trie* root=ptries[tme[ver].se];
  73.     in ans=0,v=k;
  74.     trie* temp=root;
  75.     for(in i=19; i>=0; i--)
  76.     {
  77.         bool bit=v&(1<<i);
  78.         if(temp->arr[!bit]!=NULL && (temp->arr[!bit]->mst)>=tme[ver].fi)//opposite bit there and maxStartTime >=startTime of ver
  79.         {
  80.             ans=ans|(1<<i);
  81.             temp=temp->arr[!bit];
  82.         }
  83.         else
  84.             temp=temp->arr[bit];
  85.     }
  86.     return {temp->minver,ans};
  87. }
  88.  
  89. int main() {
  90.     // your code goes here
  91.     in t;
  92.     cin>>t;
  93.     while(t--)
  94.     {
  95.         ar.clear();
  96.         ptries.clear();
  97.         val.clear();
  98.         for(in i=0; i<maxn; i++)
  99.         {
  100.             adj[i].clear();
  101.             tme[i]=mp(0,0);
  102.             flag[i]=0;
  103.         }
  104.         in n,q;
  105.         cin>>n>>q;
  106.         for(in i=1; i<=n; i++)
  107.             cin>>val[i];
  108.         for(in i=1; i<n; i++)
  109.         {
  110.             in a,b;
  111.             cin>>a>>b;
  112.             adj[a].pb(b);
  113.             adj[b].pb(a);
  114.         }
  115.         dfs(1,0);
  116.         for (int i = 0; i < 2*n; i++) {
  117.             if (tme[ar[i]].fi == 0)
  118.                 tme[ar[i]].fi = i+1;
  119.             else
  120.                 tme[ar[i]].se = i+1;
  121.         }
  122.         ptries[1]=insert(new trie(),ar[0]);
  123.         in j=0;
  124.         for(in i=1; i<2*n; i++)
  125.         {
  126.             if(flag[ar[i]])
  127.             {
  128.                 ptries[i+1]=ptries[i];
  129.             }
  130.             else
  131.             {
  132.                 flag[ar[i]]=1;
  133.                 ptries[i+1]=insert(ptries[i],ar[i]);
  134.             }
  135.  
  136.         }
  137.         in xl=0,vl=0;
  138.         for(in i=1; i<=q; i++)
  139.         {
  140.             in a,b;
  141.             cin>>a>>b;
  142.             in v=a^vl,k=b^xl;
  143.             auto pp=querytrie(v,k);
  144.             cout<<pp .fi<<" "<<pp.se<<endl;
  145.             xl=pp.se;
  146.             vl=pp.fi;
  147.         }
  148.     }
  149.     return 0;
  150. }
Runtime error #stdin #stdout 0s 29312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7LEfrR
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!