Submission #965538

#	Time	Username	Problem	Language	Result	Execution time	Memory
965538		noyancanturk	Klasika (COCI20_klasika)	C++17	33 / 110	1128 ms	524288 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>;

int ans;

vector<bool>lasn;

struct trie{

    struct node{
        node*c[2]{0,0};
    };

    using pnode=node*;
    pnode root;

    trie(){root=new node();}

    void insert(int x){
        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];
        }
    }

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

};

struct segtree{
    trie tree[2*lim];
    int n;
    segtree(int n):n(n){}
    void update(int p,int val){
        for(p+=n;p;p>>=1)tree[p].insert(val);
    }
    int query(int l,int r,int x){
        int ans=0;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
            if(l&1){
                ans=max(ans,tree[l++].search(x));
            }
            if(r&1){
                ans=max(ans,tree[--r].search(x));
            }
        }
        return ans;
    }
}*st;

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

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

void dfs(int node){
    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);
    st=new segtree(tt+100);
    st->update(tin[1],0);
    curnode=2;
    for(int i=0;i<n;i++){
        if(!q[i].ty){
            st->update(tin[curnode],dist[curnode]);
            curnode++;
        }else{
            cout<<st->query(tin[q[i].y],tout[q[i].y],dist[q[i].x])<<"\n";
        }
    }
}

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