Submission #1119057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119057		ttamx	Klasika (COCI20_klasika)	C++17	0 / 110	398 ms	188520 KiB

klasika

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n,q;
vector<tuple<int,int,int>> qr;
int val[N];
vector<int> adj[N];
int tin[N],tout[N],pos[N];
int timer=0;
set<int> alive;

struct Trie{
    struct Node;
    using Ptr = Node*;
    struct Node{
        int cnt;
        array<Ptr,2> ch;
        Node():cnt(0),ch{nullptr,nullptr}{}
    };
    Ptr root[N];
    Ptr clone(Ptr o){
        if(o)return new Node(*o);
        else return new Node();
    }
    int get_cnt(Ptr t){
        return t?t->cnt:0;
    }
    Ptr get_ch(Ptr t,int i){
        return t?t->ch[i]:nullptr;
    }
    Ptr update(Ptr o,int x){
        Ptr rt=clone(o);
        Ptr u=rt;
        u->cnt++;
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            u->ch[c]=clone(o=get_ch(o,c));
            u=u->ch[c];
            u->cnt++;
        }
        return rt;
    }
    int query(Ptr tl,Ptr tr,int x){
        int res=0;
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            if(get_cnt(get_ch(tr,c^1))-get_cnt(get_ch(tl,c^1))){
                tl=get_ch(tl,c^1);
                tr=get_ch(tr,c^1);
                res|=1<<i;
            }else{
                tl=get_ch(tl,c);
                tr=get_ch(tr,c);
            }
        }
        return res;
    }
}tr;

void dfs(int u){
    tin[u]=++timer;
    pos[timer]=u;
    for(auto v:adj[u]){
        dfs(v);
    }
    tout[u]=timer;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> q;
    qr.resize(q);
    n=1;
    for(auto &[o,x,y]:qr){
        string op;
        cin >> op >> x >> y;
        if(op=="Add"){
            o=0;
            val[++n]=val[x]^y;
            adj[x].emplace_back(n);
            x=n;
        }else{
            o=1;
        }
    }
    dfs(1);
    tr.root[0]=nullptr;
    for(int i=1;i<=n;i++){
        tr.root[i]=tr.update(tr.root[i-1],val[pos[i]]);
    }
    alive.emplace(tin[1]);
    for(auto &[o,x,y]:qr){
        if(o==0){
            alive.emplace(tin[x]);
        }else{
            int l=tin[y];
            int r=*prev(alive.upper_bound(tout[y]));
            cout << tr.query(tr.root[l-1],tr.root[r],val[x]) << "\n";
        }
    }
}

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