fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ntr "\n"
  4. #define mod (ll)(1e9+7)
  5. #define taskname "temp"
  6. #define frep freopen("input.inp","r",stdin); freopen(taskname".out","w",stdout);
  7. using namespace std;
  8. struct node{
  9.     ll child[2];
  10.     ll cnt;
  11. };
  12. struct vert{
  13.     ll child,type,val;
  14. };
  15. node trie[3000009];
  16. ll ans[100001];
  17. vector<vert> adj[100001];
  18. vector<ll> avail;
  19. ll n,q,nn=0;
  20. ll newnode(){
  21.     if(avail.size()){
  22.         ll pos=avail.back();
  23.         avail.pop_back();
  24.         trie[pos].child[0]=trie[pos].child[1]=trie[pos].cnt=0;
  25.         return pos;
  26.     }
  27.     else{
  28.         nn++;
  29.         trie[nn].child[0]=trie[nn].child[1]=trie[nn].cnt=0;
  30.         return nn;
  31.     }
  32. }
  33. void add(ll num){
  34.     ll pos=0;
  35.     for(int i=29;i>=0;i--){
  36.         if(num&(1<<i)){
  37.             if(trie[pos].child[1]==0){
  38.                 trie[pos].child[1]=newnode();
  39.             }
  40.             pos=trie[pos].child[1];
  41.             trie[pos].cnt++;
  42.         }
  43.         else{
  44.             if(trie[pos].child[0]==0){
  45.                 trie[pos].child[0]=newnode();
  46.             }
  47.             pos=trie[pos].child[0];
  48.             trie[pos].cnt++;
  49.         }
  50.     }
  51. }
  52. bool del(ll id,ll num,ll pos){
  53.     if(id>=0){
  54.         if(num&(1<<id)){
  55.             if(del(id-1,num,trie[pos].child[1])) trie[pos].child[1]=0;
  56.         }
  57.         else{
  58.             if(del(id-1,num,trie[pos].child[0])) trie[pos].child[0]=0;
  59.         }
  60.     }
  61.     trie[pos].cnt--;
  62.     if(trie[pos].cnt==0){
  63.         avail.push_back(pos);
  64.         return true;
  65.     }
  66.     return false;
  67. }
  68. ll get(ll num){
  69.     ll pos=0,ans=0;
  70.     for(int i=29;i>=0;i--){
  71.         if(num&(1<<i)){
  72.             if(trie[pos].child[1]){
  73.                 pos=trie[pos].child[1];
  74.             }
  75.             else{
  76.                 ans|=(1<<i);
  77.                 pos=trie[pos].child[0];
  78.             }
  79.         }
  80.         else{
  81.             if(trie[pos].child[0]){
  82.                 pos=trie[pos].child[0];
  83.             }
  84.             else{
  85.                 ans|=(1<<i);
  86.                 pos=trie[pos].child[1];
  87.             }
  88.         }
  89.     }
  90.     return ans;
  91. }
  92. void trav(ll u,ll num){
  93.     for(auto v:adj[u]){
  94.         if(v.type==1){
  95.             ans[v.child]=min(ans[u],v.val);
  96.             add(num^v.val);
  97.             trav(v.child,num);
  98.             del(29,num^v.val,0);
  99.         }
  100.         else{
  101.             ans[v.child]=get(num^v.val);
  102.             trav(v.child,num^v.val);
  103.         }
  104.     }
  105. }
  106. int main(){
  107.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  108.     //frep;
  109.     trie[0].child[0]=trie[0].child[1]=trie[0].cnt=0;
  110.     cin>>n>>q;
  111.     ans[0]=1e18;
  112.     for(int i=0;i<n;i++){
  113.         ll x;
  114.         cin>>x;
  115.         ans[0]=min(ans[0],x);
  116.         add(x);
  117.     }
  118.     for(int i=1;i<=q;i++){
  119.         ll type,u,num;
  120.         cin>>type>>u>>num;
  121.         adj[u].push_back({i,type,num});
  122.     }
  123.     trav(0,0);
  124.     for(int i=0;i<=q;i++){
  125.         cout<<ans[i]<<' ';
  126.     }
  127. }
  128.  
Success #stdin #stdout 0.01s 8256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/K22RYN
language:
C++14 (gcc 8.3)
created:
1 year 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!