Submission #1119071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119071		ttamx	Klasika (COCI20_klasika)	C++17	33 / 110	1029 ms	524288 KiB

klasika

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n,q,m;
vector<tuple<int,int,int>> qr[N];
int val[N];
vector<int> adj[N];
int timer=0;
int ans[N];

struct Trie{
    struct Node;
    using Ptr = Node*;
    struct Node{
        int t;
        array<Ptr,2> ch;
        Node():t(N),ch{nullptr,nullptr}{}
    };
    Ptr root;
    vector<pair<int,int>> dat;
    Trie():root(new Node()),dat(){}
    int get_t(Ptr u){
        return u?u->t:N;
    }
    void update(int x,int t){
        dat.emplace_back(x,t);
        Ptr u=root;
        u->t=min(u->t,t);
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            if(!u->ch[c])u->ch[c]=new Node();
            u=u->ch[c];
            u->t=min(u->t,t);
        }
    }
    int query(int x,int t){
        int res=0;
        Ptr u=root;
        assert(u->t<=t);
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            if(get_t(u->ch[c^1])<=t){
                u=u->ch[c^1];
                res|=1<<i;
            }else{
                u=u->ch[c];
            }
        }
        return res;
    }
    int size(){
        return dat.size();
    }
}dp[N];

void swap(Trie &l,Trie &r){
    swap(l.root,r.root);
    swap(l.dat,r.dat);
}

void dfs(int u){
    dp[u].update(val[u],u);
    for(auto v:adj[u]){
        dfs(v);
        if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]);
        for(auto [x,t]:dp[v].dat){
            dp[u].update(x,t);
        }
    }
    for(auto [x,t,i]:qr[u]){
        ans[i]=dp[u].query(x,t);
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> q;
    n=1;
    for(int i=1;i<=q;i++){
        string op;
        int x,y;
        cin >> op >> x >> y;
        if(op=="Add"){
            val[++n]=val[x]^y;
            adj[x].emplace_back(n);
        }else{
            qr[y].emplace_back(val[x],n,++m);
        }
    }
    dfs(1);
    for(int i=1;i<=m;i++){
        cout << ans[i] << "\n";
    }
}

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