Submission #1094105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094105		0pt1mus23	Klasika (COCI20_klasika)	C++14	110 / 110	1905 ms	446028 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
#define needforspeed ios::sync_with_stdio(0);cin.tie(0);
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9 +7,sze = 2e5 +23,inf = INT_MAX, L = 31; 

struct T {
    T *child[2];
    set<int> fener;
    T(){
        child[0] = child[1] = nullptr;
    }
};

T *root = new T();
int tnod = 1;
vector<pair<int, int>> graph[sze];
int discover[sze], finish[sze], pref[sze];
int timer = 0;

void add(T *node, int bit, int val, int gir){
    if (bit < 0) {
        return;
    }
    int x = 0;
    if(val & (1<<bit)){
        x=1;
    }
    if(!node->child[x]) {
        node->child[x] = new T();
    }
    node->child[x]->fener.ins(gir);
    add(node->child[x], bit - 1, val, gir);
}


int qry(T *node, int bit, int val, int l, int r){
    if(bit < 0) {
        return 0;
    }
    int lazim = (val & (1 << bit)) ? 0 : 1;
    if(node->child[lazim] && node->child[lazim]->fener.lower_bound(l) != node->child[lazim]->fener.upper_bound(r)){
        return (1 << bit) + qry(node->child[lazim], bit - 1, val, l, r);
    }
    else{
        return qry(node->child[1 - lazim], bit - 1, val, l, r);
    }
}

void dfs(int node,int par,int px){
    discover[node]=++timer;
    pref[node]=px;
    for(auto v:graph[node]){
        if(v.first!=par){
            dfs(v.first,node,px ^ v.second);
        }
    }
    finish[node]=++timer;   
}
void opt1z(){
    int q;
    cin>>q;
    int nodec =2;
    vector<pair<int, pair<int,int>>> queries;
    for(int i=0;i<q;i++){
        string op;cin>>op;
        int a,b;
        cin>>a>>b;
        if(op=="Add"){
            graph[a].pb({nodec,b});
            graph[nodec].pb({a,b});
            queries.pb({0,{nodec,b}});
            nodec++;
        }
        else{
            queries.pb({1,{a,b}});
        }
    }
    dfs(1,-1,0);
    add(root,L,0,discover[1]);
    // cout<<pref[2]<<endl;
    for(auto v:queries){
        auto [a,b] = v.second;
        if(v.first ==0){
            add(root,L,pref[a],discover[a]);
        }
        else{
            // cout<<"sa"<<endl;
            cout<<qry(root,L,pref[a],discover[b],finish[b])<<endl;
        }
    }
}
 
signed main() {
    needforspeed;
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void opt1z()':
klasika.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |         auto [a,b] = v.second;
      |              ^

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