Submission #713230

#	Time	Username	Problem	Language	Result	Execution time	Memory
713230		gokussjz	Klasika (COCI20_klasika)	C++17	110 / 110	4123 ms	517320 KiB

klasika

//  ॐ
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846
#define ll long long int
 
 
const int N=2e5+5;
vector<pair<int,int>> adj[N];
int tin[N],tout[N],val[N];
int curr=0;
 
static const int K = 2;      // check
static const int bits = 30;  // check

struct node{

    array<int,K> next;
    int cnt;
    set<pair<int,int>> s;
};

struct TRIE{

     vector<node> trie;
     int root,sz;

     inline node create(){
        node ret;
        ret.cnt=0;
        ret.s.clear();
        for(int i=0;i<K;i++){
            ret.next[i]=-1;
        }

        return ret;
     }

     inline void init(){

          trie.clear();
          trie.push_back(create());
          sz=1;
          root=0;
     }

     void insert(int val,int id){

         int v=root;
         ++trie[v].cnt;
         trie[v].s.insert({tin[id],tout[id]});

         for(int i=bits;i>=0;i--){
              int temp=val&(1<<i) ? 1 : 0;
              if(trie[v].next[temp]==-1){
                   trie.push_back(create());
                   trie[v].next[temp]=(sz++);
              }
              v=trie[v].next[temp];
              trie[v].s.insert({tin[id],tout[id]});
              ++trie[v].cnt;
         }
     }

     void erase(int val,int id){

         int v=root;
         --trie[v].cnt;
         trie[v].s.erase({tin[id],tout[id]});
         for(int i=bits;i>=0;i--){
            int temp=val&(1<<i) ? 1 : 0;
            v=trie[v].next[temp];
            trie[v].s.erase({tin[id],tout[id]});
            --trie[v].cnt;
         }
     }

    int max_query(int val,int y){

          int ret=0,v=root;
          for(int i=bits;i>=0;i--){
              int temp=val&(1<<i) ? 0 : 1;
              bool poss=0;
              if(trie[v].next[temp]!=-1){
                    auto it=trie[trie[v].next[temp]].s.lower_bound({tin[y],tout[y]});
                    if(it!=trie[trie[v].next[temp]].s.end()){
                          int end=(*it).second;
                          if(end<=tout[y]){
                                poss=1;
                          }
                    }
              }

              if(!poss){
                 temp^=1;
              }

              else{
                ret+=(1<<i);
              }

              v=trie[v].next[temp];

          }
          return ret;            
     }
};

void dfs(int v,int p,int xr){
     tin[v]=(++curr);
     val[v]=xr;
     for(auto [u,w] : adj[v]){
          if(u==p)
             continue;
          dfs(u,v,(xr^w));
     }
     tout[v]=(++curr);

}


int main(){
   
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int test = 1;
    // cin>>test;
 
 
    while(test--){
                    
                    int q;
                    cin>>q;

                    vector<array<int,3>> v;
                    int tot=1;

                    for(int i=0;i<q;i++){
                         string s;
                         int a,b;
                         cin>>s>>a>>b;
                         if(s[0]=='A'){
                             ++tot;
                             v.push_back({1,tot,b});
                             adj[a].push_back({tot,b});
                             adj[tot].push_back({a,b});
                         }
                         else{
                             v.push_back({2,a,b});
                         }
                    }

                    vector<int> ans;
                    TRIE tr;
                    tr.init();

                    reverse(v.begin(),v.end());
                    dfs(1,1,0);

                    for(int i=1;i<=tot;i++){
                        tr.insert(val[i],i);
                    }

                    for(auto [type,a,b] : v){
                          if(type==1){
                               // cout<<a<<' '<<val[a]<<'\n';
                               tr.erase(val[a],a);
                          }

                          else{
                              ans.push_back(tr.max_query(val[a],b));
                          }
                    }

                    reverse(ans.begin(),ans.end());
                    for(auto u : ans){
                        cout<<u<<'\n';
                    }

                    // cout<<'\n'; 
                  
        
   }
        return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44