fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. //using namespace __gnu_pbds;
  5. using namespace std;
  6. using ll=long long;
  7. //typedef tree<int,null_type,less_equal<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  8. #define mem(a,x)       memset(a,x,sizeof(a))
  9. #define fast(s)        s.reserve(2000); s.max_load_factor(0.5);
  10. #define F              first
  11. #define S              second
  12. #define pii            pair<int,int>
  13. #define iii            tuple<int,int,int>
  14. #define all(p)         p.begin(), p.end()
  15. template<typename T> bool maximum(T &A, const T &B) {return A<B? A=B, true: false;}
  16. template<typename T> bool minimum(T &A, const T &B) {return A>B? A=B, true: false;}
  17. template<typename T> T gcd(T t) {return t;}
  18. template<typename T, typename... Args> T gcd(T t, Args... args) {return __gcd(t,args...);};
  19. void print(bool condition=1) {cout<<(condition? "YES\n": "NO\n");}
  20. const int mod=1e9+7;
  21. const int INF=1e9;
  22. const int N=2e5+5, LOG=30;
  23. int n, q, numQuery, res[N], z[N], h[N], cnt[N], a[N], in[N], out[N], Time;
  24. vector<int> e[N];
  25. vector<iii> query[N];
  26. void file()
  27. {
  28.     #define task "codeforces"
  29.     if(fopen(task".inp","r"))
  30.     {
  31.         freopen(task".inp","r",stdin);
  32.         freopen(task".out","w",stdout);
  33.     }
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);
  36.     cout.tie(0);
  37. }
  38. struct Trie
  39. {
  40.     int mn[N*LOG], child[N*LOG][2];
  41.     int root, idx;
  42.     int new_node()
  43.     {
  44.         ++idx;
  45.         mn[idx]=INF;
  46.         child[idx][0]=child[idx][1]=0;
  47.         return idx;
  48.     }
  49.     void reset()
  50.     {
  51.         idx=0;
  52.         root=new_node();
  53.     }
  54.     void add(int x, int y)
  55.     {
  56.         int p=root;
  57.         for(int i=LOG; i>=0; --i)
  58.         {
  59.             int c=x>>i&1;
  60.             if(!child[p][c]) child[p][c]=new_node();
  61.             p=child[p][c];
  62.             minimum(mn[p],y);
  63.         }
  64.     }
  65.     int getMax(int x, int y)
  66.     {
  67.         int ans=0, p=root;
  68.         for(int i=LOG; i>=0; --i)
  69.         {
  70.             int c=x>>i&1;
  71.             if(child[p][c^1] && mn[child[p][c^1]]<=y)
  72.             {
  73.                 p=child[p][c^1];
  74.                 ans|=(1<<i);
  75.             }
  76.             else if(child[p][c] && mn[child[p][c]]<=y)
  77.                 p=child[p][c];
  78.             else
  79.                 return ans;
  80.         }
  81.         return ans;
  82.     }
  83. } T;
  84. void dfs_init(int u)
  85. {
  86.     ++Time;
  87.     in[u]=Time;
  88.     a[Time]=u;
  89.     cnt[u]=1;
  90.     for(int v: e[u])
  91.     {
  92.         dfs_init(v);
  93.         cnt[u]+=cnt[v];
  94.     }
  95.     out[u]=Time;
  96. }
  97. void DFS(int u)
  98. {
  99.     int nxt=0;
  100.     for(int v: e[u])
  101.         if(cnt[v]>cnt[nxt]) nxt=v;
  102.     for(int v: e[u])
  103.     {
  104.         if(v==nxt) continue;
  105.         DFS(v);
  106.         T.reset();
  107.     }
  108.     if(nxt) DFS(nxt);
  109.     for(int v: e[u])
  110.     {
  111.         if(v==nxt) continue;
  112.         for(int k=in[v]; k<=out[v]; ++k)
  113.             T.add(h[a[k]],z[a[k]]);
  114.     }
  115.     T.add(h[u],z[u]);
  116.     for(auto &[v,k,id]: query[u])
  117.         res[id]=T.getMax(h[v],k);
  118. }
  119. void Solve()
  120. {
  121.     cin>>q;
  122.     n=1;
  123.     for(int i=1; i<=q; ++i)
  124.     {
  125.         string type;
  126.         int x, y;
  127.         cin>>type>>x>>y;
  128.         if(type=="Add")
  129.         {
  130.             ++n;
  131.             z[n]=i;
  132.             h[n]=h[x]^y;
  133.             e[x].push_back(n);
  134.         }
  135.         else query[y].push_back({x,i,++numQuery});
  136.     }
  137.     dfs_init(1);
  138.     T.reset();
  139.     DFS(1);
  140.     for(int i=1; i<=numQuery; ++i)
  141.         cout<<res[i]<<"\n";
  142. }
  143. signed main()
  144. {
  145.     file();
  146.     Solve();
  147.     return 0;
  148. }
Success #stdin #stdout 0.01s 19896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TbvNhW
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

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!