oj.uz

Submission #202815

# Submission time Handle Problem Language Result Execution time Memory
202815 2020-02-18T01:32:05 Z EmmanuelAC Klasika (COCI20_klasika) C++14
0 / 110
 379 ms 524292 KB 
#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){

    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 ++;

        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 || 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

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -