oj.uz

Submission #202818

# Submission time Handle Problem Language Result Execution time Memory
202818 2020-02-18T01:40:11 Z EmmanuelAC Klasika (COCI20_klasika) C++14
110 / 110
 3884 ms 482752 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(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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 9 ms 5500 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 9 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 9 ms 5496 KB Output is correct
11 Correct 10 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 9 ms 5500 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 9 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 9 ms 5496 KB Output is correct
11 Correct 10 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 12 ms 6676 KB Output is correct
14 Correct 14 ms 8144 KB Output is correct
15 Correct 16 ms 8524 KB Output is correct
16 Correct 20 ms 11336 KB Output is correct
17 Correct 12 ms 6672 KB Output is correct
18 Correct 15 ms 8144 KB Output is correct
19 Correct 17 ms 8392 KB Output is correct
20 Correct 18 ms 9420 KB Output is correct
21 Correct 12 ms 6676 KB Output is correct
22 Correct 15 ms 8140 KB Output is correct
23 Correct 17 ms 8392 KB Output is correct
24 Correct 20 ms 9452 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 118916 KB Output is correct
2 Correct 2104 ms 239212 KB Output is correct
3 Correct 2722 ms 295340 KB Output is correct
4 Correct 3537 ms 482540 KB Output is correct
5 Correct 1156 ms 119236 KB Output is correct
6 Correct 1980 ms 234312 KB Output is correct
7 Correct 2700 ms 289088 KB Output is correct
8 Correct 3559 ms 472968 KB Output is correct
9 Correct 1163 ms 119732 KB Output is correct
10 Correct 1978 ms 235056 KB Output is correct
11 Correct 2727 ms 291548 KB Output is correct
12 Correct 3506 ms 474704 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 9 ms 5500 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 9 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 9 ms 5496 KB Output is correct
11 Correct 10 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 12 ms 6676 KB Output is correct
14 Correct 14 ms 8144 KB Output is correct
15 Correct 16 ms 8524 KB Output is correct
16 Correct 20 ms 11336 KB Output is correct
17 Correct 12 ms 6672 KB Output is correct
18 Correct 15 ms 8144 KB Output is correct
19 Correct 17 ms 8392 KB Output is correct
20 Correct 18 ms 9420 KB Output is correct
21 Correct 12 ms 6676 KB Output is correct
22 Correct 15 ms 8140 KB Output is correct
23 Correct 17 ms 8392 KB Output is correct
24 Correct 20 ms 9452 KB Output is correct
25 Correct 1286 ms 118916 KB Output is correct
26 Correct 2104 ms 239212 KB Output is correct
27 Correct 2722 ms 295340 KB Output is correct
28 Correct 3537 ms 482540 KB Output is correct
29 Correct 1156 ms 119236 KB Output is correct
30 Correct 1980 ms 234312 KB Output is correct
31 Correct 2700 ms 289088 KB Output is correct
32 Correct 3559 ms 472968 KB Output is correct
33 Correct 1163 ms 119732 KB Output is correct
34 Correct 1978 ms 235056 KB Output is correct
35 Correct 2727 ms 291548 KB Output is correct
36 Correct 3506 ms 474704 KB Output is correct
37 Correct 1898 ms 122448 KB Output is correct
38 Correct 2691 ms 239272 KB Output is correct
39 Correct 3238 ms 297992 KB Output is correct
40 Correct 3731 ms 482752 KB Output is correct
41 Correct 2012 ms 120044 KB Output is correct
42 Correct 2823 ms 234460 KB Output is correct
43 Correct 3313 ms 289384 KB Output is correct
44 Correct 3807 ms 473068 KB Output is correct
45 Correct 2202 ms 120392 KB Output is correct
46 Correct 2998 ms 235364 KB Output is correct
47 Correct 3503 ms 290376 KB Output is correct
48 Correct 3884 ms 474776 KB Output is correct