Submission #1033811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033811		doducanh	Klasika (COCI20_klasika)	C++14	110 / 110	1811 ms	439380 KiB

klasika

///breaker
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ii pair<int,int>
#define bit(x,i) ((x>>i)&1)
struct queries
{
    bool type;
    int u,v;
};
const int maxn=2e5+3;
int n;
queries e[maxn];
vector<ii>adj[maxn];
struct node{
    set<int>se;
    node *one,*zero;
    node(){
        zero=one=NULL;
    }
}root;
void add(node *curr,int i,int x,int &pos){
    curr->se.insert(pos);
    if(i<0)return;
    if(!bit(x,i)){
        if(curr->zero==NULL)curr->zero=new node();
        add(curr->zero,i-1,x,pos);
    }
    else{
        if(curr->one==NULL)curr->one=new node();
        add(curr->one,i-1,x,pos);
    }
}
int get(node *curr,int i,int &val,int &l,int &r){
    if(i<0)return 0;
    if(bit(val,i)==0){
        if(curr->one==NULL||(curr->one->se.lower_bound(l)==curr->one->se.upper_bound(r)))return get(curr->zero,i-1,val,l,r);
        else return ((1<<i)+get(curr->one,i-1,val,l,r));
    }
    else{
        if(curr->zero==NULL||(curr->zero->se.lower_bound(l)==curr->zero->se.upper_bound(r)))return get(curr->one,i-1,val,l,r);
        else return ((1<<i)+get(curr->zero,i-1,val,l,r));
    }
}
int cnt=0;
int d[maxn];
int in[maxn],out[maxn];
void dfs(int u,int par)
{
    in[u]=++cnt;
    for(ii a:adj[u]){
        int v=a.fi;
        int w=a.se;
        d[v]=d[u]^w;
        dfs(v,u);
    }
    out[u]=cnt;
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1,j=2;i<=n;i++){
        string s;
        cin>>s;
        cin>>e[i].u>>e[i].v;
        if(s[0]=='A'){
            e[i].type=false;
            adj[e[i].u].push_back({j,e[i].v});
            j++;
        }
        else e[i].type=true;
    }
    d[1]=0;
    dfs(1,0);
    add(&root,30,0,in[1]);
    for(int i=1,j=2;i<=n;i++){
        if(e[i].type==0){
            add(&root,30,d[j],in[j]);
            j++;
        }
        else{
            cout<<get(&root,30,d[e[i].u],in[e[i].v],out[e[i].v])<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

klasika.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main(){
      | ^~~~

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