Submission #965700

#	Time	Username	Problem	Language	Result	Execution time	Memory
965700		noyancanturk	Klasika (COCI20_klasika)	C++17	110 / 110	2009 ms	429072 KiB

klasika

#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;

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);
    tr.insert(0,0);
    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: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44