oj.uz

Submission #965699

# Submission time Handle Problem Language Result Execution time Memory
965699 2024-04-19T05:38:26 Z noyancanturk Klasika (COCI20_klasika) C++17
0 / 110
 447 ms 125856 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=2e5+500;
const int mod=1e9+7;
const int llim=3e7; 

using pii=pair<int,int>;

struct trie{
 
    struct node{
        set<int>st;
        node*c[2]{0,0};
    };
 
    using pnode=node*;
    pnode root;
 
    trie(){root=new node();}
 
    void insert(int x,int y){
        pnode cur=root;
        for(int i=29;0<=i;i--){
            if(!cur->c[(x>>i)&1]){
                cur->c[(x>>i)&1]=new node();
            }
            cur=cur->c[(x>>i)&1];
            cur->st.insert(y);
        }
    }
 
    bool check(pnode p,int l,int r){
        if(!p)return 0;
        auto k=p->st.lower_bound(l);
        return k!=p->st.end()&&*k<=r;
    }

    int search(int x,int l,int r){
        pnode cur=root;
        int ans=0;
        for(int i=29;0<=i;i--){
            if(check(cur->c[!((x>>i)&1)],l,r)){
                if(!((x>>i)&1))ans+=1<<i;
                cur=cur->c[!((x>>i)&1)];
            }else if(check(cur->c[(x>>i)&1],l,r)){
                if((x>>i)&1)ans+=1<<i;
                cur=cur->c[(x>>i)&1];
            }else{
                return 0;
            }
        }
        return ans^x;
    }
 
}tr;

struct qdata{
    int ty,x,y;
};

vector<pii>v[lim];
int dist[lim];
int tin[lim],tout[lim],tt=0;

void dfs(int node){
    //cerr<<node<<"\n";
    tin[node]=tt++;
    for(auto[j,c]:v[node]){
        dist[j]=dist[node]^c;
        dfs(j);
    }
    tout[node]=tt-1;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin); freopen(".out","w",stdout);
#endif
    int n;
    cin>>n;
    qdata q[n];
    int curnode=2;
    for(int i=0;i<n;i++){
        string ty;
        cin>>ty>>q[i].x>>q[i].y;
        if(ty=="Add"){
            q[i].ty=0;
            v[q[i].x].pb({curnode,q[i].y});
            curnode++;
        }else{
            q[i].ty=1;
        }
    }
    dfs(1);
    curnode=2;
    for(int i=0;i<n;i++){
        if(!q[i].ty){
            tr.insert(dist[curnode],tin[curnode]);
            curnode++;
        }else{
            cout<<tr.search(dist[q[i].x],tin[q[i].y],tout[q[i].y])<<"\n";
        }
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Incorrect 2 ms 7772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Incorrect 2 ms 7772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 447 ms 125856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Incorrect 2 ms 7772 KB Output isn't correct
3 Halted 0 ms 0 KB -