Submission #643266

#	Time	Username	Problem	Language	Result	Execution time	Memory
643266		Phucdang2k5	Klasika (COCI20_klasika)	C++17	110 / 110	2830 ms	475332 KiB

klasika

//  ---PhucDang---  //
#include<bits/stdc++.h>
#define name "practice"
#define maxn 200010
#define oo LLONG_MAX
#define INF INT_MAX
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define CONST
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define e endl
using namespace std;
typedef long long ll;
template<class T> void MIN(T &A, T B) {A=min(A,B);}
template<class T> void MAX(T &A, T B) {A=max(A,B);}
template<class T> void SUM(T &A, T B) {A=A+B;}
template<class T> void HIEU(T &A, T B) {A=A-B;}
int dis[maxn],q;
vector<int>vec[maxn];

struct Data{
    bool type;
    int u,v;
};
vector<Data>Q;
int tail[maxn],num[maxn],timedfs=0;

void preDFS(int u, int par){
    num[u]=++timedfs;
    for(int v: vec[u]){
        if(v==par) continue;
        preDFS(v,u);
    }
    tail[u]=timedfs;
}

void pre(void){
    int curr=1;
    fo(i,1,q){
        string type;
        int a,b;
        cin>>type>>a>>b;
        if(type=="Add"){
            ++curr;
            vec[a].pb(curr);
            vec[curr].pb(a);
            dis[curr]=dis[a]^b;
            Q.pb({false,a,curr});
        }
        else Q.pb({true,a,b});
    }
    preDFS(1,0);
}

struct node{
    int a[2];
    set<int>id;
    node(){
        a[0]=a[1]=0;
        id.clear();
    }
};
vector<node>trie;

void add(int pos, int depth, int val, int num){
    trie[pos].id.insert(num);
    if(depth==0) return;
    bool bit=(val>>(depth-1))&1;
    int u=trie[pos].a[bit];
    if(u==0){
        trie.pb(node());
        trie[pos].a[bit]=trie.size()-1;
        u=trie.size()-1;
    }
    add(u,depth-1,val,num);
}

bool check(set<int> &s, int l, int r){
    if(s.lower_bound(l)==s.upper_bound(r)) return false;
    return true;
}

int get(int pos, int depth, int l, int r, int xorval){
    if(depth==0) return 0;
    int u1=trie[pos].a[1];
    int u0=trie[pos].a[0];
    if((xorval>>(depth-1))&1) swap(u1,u0);
    if(u1&&check(trie[u1].id,l,r)){
        return (1<<(depth-1))+get(u1,depth-1,l,r,xorval);
    }
    else{
        return get(u0,depth-1,l,r,xorval);
    }
}

void process(void){
    pre();
    trie.pb(node());
    add(0,30,dis[1],num[1]);
    for(auto [type,u,v]: Q){
        if(type==false) add(0,30,dis[v],num[v]);
        else cout<<get(0,30,num[v],tail[v],dis[u])<<e;

    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);  cout.tie(0);
//    freopen(name".inp","r",stdin);
//    freopen(name".out","w",stdout);
    cin>>q;
    process();
}

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