Submission #1098380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098380		0pt1mus23	Klasika (COCI20_klasika)	C++14	33 / 110	2334 ms	524288 KiB

klasika

// checking trie mem without pointers
#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 = 8e5 +23,inf = INT_MAX, L = 31; 
unordered_map<int, map<int,int> > T;
unordered_map<int, map<int, set<int>>> fener;
int tnod = 1;
int discover[sze];
int finish[sze];
vector<pair<int,int>> graph[sze];
 
void add(int node,int bit,int val,int gir){
    if(bit<0){
        return;
    }
    int x =0;
    if(val & (1<<bit)){
        x=1;
    }
    if(T[node][x]==0){
       T[node][x]= ( ++tnod);
    }
    // cout<<bit<<" added "<<val<<" "<<x<<endl;
    fener[node][x].ins(gir);
    add(T[node][x],bit-1,val,gir);
}
int timer =0;
int pref[sze];
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;   
}
 
int qry(int node,int bit,int val,int l,int r){
    if(bit<0){
        return 0;
    }
    int lazim =1;
    if(val & (1<<bit)){
        lazim=0;
    }
    // cout<<bit<<" "<<val<<" "<<lazim<<" "<<T[node][lazim]<<endl;
    if(T[node][lazim] && fener[node][lazim].lower_bound(l) != fener[node][lazim].upper_bound(r)){
        return (1<<bit) + qry(T[node][lazim],bit-1,val,l,r);
    }
    else{
        return qry(T[node][1 - lazim],bit-1,val,l,r);
    }
}
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(1,L,0,discover[1]);
    // cout<<pref[2]<<endl;
    for(auto v:queries){
        auto [a,b] = v.second;
        if(v.first ==0){
            add(1,L,pref[a],discover[a]);
        }
        else{
            // cout<<"sa"<<endl;
            cout<<qry(1,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:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         auto [a,b] = v.second;
      |              ^

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