Submission #965550

#	Time	Username	Problem	Language	Result	Execution time	Memory
965550		noyancanturk	Klasika (COCI20_klasika)	C++17	33 / 110	896 ms	520500 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;
const int llim=3e7; 

using pii=pair<int,int>;

struct trie{

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

    static node nds[llim];
    static int nextnode;

    using pnode=node*;
    pnode root;

    trie(){root=nds+(nextnode++);}

    void insert(int x){
        assert(nextnode<llim);
        pnode cur=root;
        for(int i=29;0<=i;i--){
            if(!cur->c[(x>>i)&1]){
                cur->c[(x>>i)&1]=nextnode++;
            }
            cur=nds+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=nds+cur->c[!((x>>i)&1)];
            }else if(cur->c[(x>>i)&1]){
                if((x>>i)&1)ans+=1<<i;
                cur=nds+cur->c[(x>>i)&1];
            }else{
                return 0;
            }
        }
        return ans^x;
    }

};

int trie::nextnode=1;
trie::node trie::nds[llim];

struct segtree{
    trie tree[2*lim];
    int 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){
    //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);
    cerr<<sizeof(trie::nds)/1000000<<"\n";
#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.n=tt+50;
    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