Submission #889568

#	Time	Username	Problem	Language	Result	Execution time	Memory
889568		dimashhh	Klasika (COCI20_klasika)	C++17	110 / 110	2107 ms	443180 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1, MOD = 998244353,b = 30;
typedef long long ll;
vector<array<int,3>> qr;
int q,tin[N],tout[N],n = 1,d[N],timer = 0;
vector<pair<int,int>> g[N];
void dfs(int v){
    tin[v] = ++timer;
    for(auto [to,w]:g[v]){
        d[to] = (d[v] ^ w);
        dfs(to);
    }
    tout[v] =timer;
}
struct node{
    node *next[2];
    set<int> st;
    node(){
        for(int i = 0;i < 2;i++){
            next[i] = nullptr;
        }
    }
};
node *root = new node();
void add(int tadd,int val){
    node *cur = root;
    cur->st.insert(tadd);
    for(int i = b;i >= 0;i--){
        int nv = ((val >> i) & 1);
        
        if(!cur->next[nv])
            cur->next[nv] = new node();
        cur = cur->next[nv];
        cur->st.insert(tadd);
    }
}
int get(int val,int l,int r){
    node *cur = root;
    if(cur->st.empty()) return 0;
    int ret = 0;
    for(int i = b;i >= 0;i--){
        int nd = ((val >> i) & 1);
        nd ^= 1;
        bool ok = false;
        if(cur->next[nd]){
            auto it = cur->next[nd]->st.lower_bound(l);
            if(it != cur->next[nd]->st.end() && *it <= r){
                ok = 1;
            }
        }
        if(ok){
            ret += (1ll << i);
            cur = cur->next[nd];
        }else{
            cur = cur->next[!nd];
        }
    }
    return ret;
}
void test(){
    cin >> q;
    for(int i = 1;i <= q;i++){
        string tp;
        cin >> tp;
        if(tp[0] == 'A'){
            ++n;
            int x,y;
            cin >> x >> y;
            g[x].push_back({n,y});
            qr.push_back({1,n,y});
        }else{
            int x,y;
            cin >> x >> y;
            qr.push_back({2,x,y});
        }
    }
    dfs(1);
    add(tin[1],0);
    for(auto i:qr){
        if(i[0] == 1){
            add(tin[i[1]],d[i[1]]);
            // cout << tin[i[1]] << ' ' << d[i[1]] << "x\n";
        }else{
            // cout << d[i[1]] << ' ' << tin[i[2]] << ' ' << tout[i[2]] << '\n';
            cout << get(d[i[1]],tin[i[2]],tout[i[2]]) << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

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