Submission #202795

#	Time	Username	Problem	Language	Result	Execution time	Memory
202795		EmmanuelAC	Klasika (COCI20_klasika)	C++14	0 / 110	330 ms	524292 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(10000005);

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

bitset<200001> vis;

void dfs(int p, int node, int val){
    //cout << p << " " << node << "\n";

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

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

    cout << "xor node : " << node << " " << x[node] << "\n";

    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){
    //cout << "node : " << node << " idx : " << idx << " bit : " << bit << "\n";

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

    //cout << ( x[idx]&(1<<bit) ) << "\n";

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

        new_node(trie[node].one, idx, bit -1);
    }
    else{
        if( trie[node].zero == -1 )
            trie[node].zero = 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 )    return 0;

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

    return 0;
}

int ans_query(int a, int b){
    //cout << "xa " << x[a] << "\n";
    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.resize(query.size() +1);
            query.pb( mp( 0, mp(x, y) ) );

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

            //query.resize(query.size() +1);
            query.pb( mp( 1, mp(a, b) ) );
        }
    }

    //cout << "ok\n";

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

    //cout << "ok\n";

    n = 1;
    for(int i=0; i<Q; i++){
        if(query[i].ft == 0){
            n++; new_node(0, n, 30);

            //for(int j=0; j<last; j++)
            //    cout << trie[j].zero << " " << trie[j].one << "\n";
        }
        else{
            //cout << "query\n";
            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:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<edges[node].size(); i++){
                  ~^~~~~~~~~~~~~~~~~~~

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