oj.uz

답안 #202796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202796 2020-02-17T23:34:54 Z EmmanuelAC Klasika (COCI20_klasika) C++14
0 / 110
 272 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){
    //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 || last == 1)    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

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 272 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 272 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 271 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 272 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -