Submission #202818

#	Time	Username	Problem	Language	Result	Execution time	Memory
202818		EmmanuelAC	Klasika (COCI20_klasika)	C++14	110 / 110	3884 ms	482752 KiB

klasika

#include<bits/stdc++.h>
using namespace std;

#define ft first
#define sd second
#define mp make_pair
#define pb push_back 
#define pii pair<int, int>

struct nodes{
    set<int> left_ids;
    int one, zero;

    nodes(){
        one = zero = -1;
    }
};

int n, t, last = 1;

vector<nodes> trie(1);

vector<pii> edges[200005];
vector< pair<int, pii> > query;
int l[200005], r[200005], x[200005];

bitset<200001> vis;

void dfs(int p, int node, int val){

    if(vis[node])   return;
    vis[node] = true;

    l[node] = t++;
    x[node] = x[p]^val;

    for(int i=0; i<edges[node].size(); i++)
        dfs(node, edges[node][i].ft, edges[node][i].sd);
    
    r[node] = t++;
}

void new_node(int node, int idx, int bit){

    trie[node].left_ids.insert(l[idx]);
    if( bit < 0 ) return;

    if(x[idx] & (1<<bit)){
        if( trie[node].one == -1 ){
            trie[node].one = last ++;
            trie.resize(last);
        }

        new_node(trie[node].one, idx, bit -1);
    }
    else{
        if( trie[node].zero == -1 ){
            trie[node].zero = last ++;
            trie.resize(last);
        }

        new_node(trie[node].zero, idx, bit -1);
    }
}

bool ask_node(int node, int b){
    return (trie[node].left_ids.lower_bound(l[b]) != trie[node].left_ids.lower_bound(r[b]));
}

int traverse(int mxor, int b, int bit, int node){
    if( bit < 0 || last <= 1)    return 0;

    if( mxor & (1<<bit) ){
        if( trie[node].zero != -1 && ask_node(trie[node].zero, b) ){
            return traverse(mxor, b, bit -1, trie[node].zero);
        }
        else{
            return (1<<bit) + traverse(mxor, b, bit -1, trie[node].one);
        }
    }
    else{
        if( trie[node].one != -1 && ask_node(trie[node].one, b) ){
            return (1<<bit) + traverse(mxor, b, bit -1, trie[node].one);
        }
        else{
            return traverse(mxor, b, bit -1, trie[node].zero);
        }
    }

    return 0;
}

int ans_query(int a, int b){
    return x[a] ^ traverse(x[a], b, 30, 0);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int Q; cin >> Q;

    n = 1;
    for(int q=0; q<Q; q++){
        string s; cin >> s;
        if(s == "Add"){
            int x, y; cin >> x >> y;
            query.pb( mp( 0, mp(x, y) ) );

            edges[x].pb( mp(++n, y) );
        }
        else{
            int a, b; cin >> a >> b;

            query.pb( mp( 1, mp(a, b) ) );
        }
    }


    vis.reset();
    dfs(0, 1, 0);

    n = 1;  new_node(0, 1, 30);
    for(int i=0; i<Q; i++){
        if(query[i].ft == 0){
            n++; new_node(0, n, 30);
        }
        else{
            cout << ans_query(query[i].sd.ft, query[i].sd.sd) << "\n";
        }
    }
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int, int)':
klasika.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<edges[node].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~

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