Submission #308335

#	Time	Username	Problem	Language	Result	Execution time	Memory
308335		ErdosSzekeres	Klasika (COCI20_klasika)	C++14	0 / 110	2799 ms	524288 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pii pair<int,int>
const int MAXN = 2e5+7;
int q;
int tp[MAXN], a[MAXN], b[MAXN], d[MAXN], t=0, ent[MAXN], sai[MAXN];
int fe[8*MAXN], fd[8*MAXN], node_counter = 0;
set<int> aux[8*MAXN];//entry times
int create(){
    node_counter++;
    fe[node_counter] = -1;
    fd[node_counter] = -1;
    aux[node_counter].insert(1<<30+1);
    return node_counter;
}
vector<pii> G[MAXN];
void inserir(int idx, int depth, int val, int et){
    aux[idx].insert(et);
    if(depth < 0)return;
    if((val&(1<<depth))){//go right
        if(fd[idx] == -1)fd[idx] = create();
        inserir(fd[idx], depth-1, val, et);
    }else{
        if(fe[idx] == -1)fe[idx] = create();
        inserir(fe[idx], depth-1, val, et);
    }
}
void dfs(int u){
    t++; ent[u] = t;
    for(pii viz : G[u]){
        d[viz.first] = (d[u]^viz.second);
        dfs(viz.first);
    }
    sai[u] = t;
}
int query(int idx, int depth, int val, int node){
    if(depth < 0)return 0;
    if((val&(1<<depth))){//i want to go left
        if(fe[idx] == -1){//but i cant
            return query(fd[idx], depth-1, val, node);
        }else{
            int tst = *aux[fe[idx]].lower_bound(ent[node]);
            if(tst>=ent[node] && tst <= sai[node]){//go!!
                //cout<<tst<<" "<<ent[node]<<" "<<sai[node]<<"  --> "<<node<<endl;
                return (1<<depth) + query(fe[idx], depth-1, val, node);
            }
            return query(fd[idx], depth-1, val, node);
        }
    }else{//i want to go right
        if(fd[idx] == -1){//but i cant
            return query(fe[idx], depth-1, val, node);
        }else{
            int tst = *aux[fd[idx]].lower_bound(ent[node]);
            if(tst>=ent[node] && tst <= sai[node]){//go!!
                //cout<<tst<<" "<<ent[node]<<" "<<sai[node]<<"  --> "<<node<<endl;
                return (1<<depth) + query(fd[idx], depth-1, val, node);
            }
            return query(fe[idx], depth-1, val, node);
        }
    }
}
int main(){
    fastio; cin>>q;
    for(int i=0; i<q; i++){
        string ii; cin>>ii>>a[i]>>b[i];
        tp[i] = (ii=="Add") ? 0 : 1;
    }
    int raiz = create();
    int id = 1;
    for(int i=0; i<q; i++){//build tree and compute euler tour
        if(tp[i] == 1)continue;
        id++;
        G[a[i]].push_back({id, b[i]});
    }
    dfs(1);
    inserir(1, 30, 0, ent[1]);
    id = 1;
    for(int i=0; i<q; i++){
        if(tp[i] == 0){
            id++;
            inserir(1, 30, d[id], ent[id]);
        }else{
            cout << query(raiz, 30, d[a[i]], b[i]) << endl;//max xor with d[a[i]] in subtree of b[i]
        }
    }
}

Compilation message (stderr)

klasika.cpp: In function 'int create()':
klasika.cpp:14:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |     aux[node_counter].insert(1<<30+1);
      |                                 ~~^~

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