oj.uz

Submission #1017301

# Submission time Handle Problem Language Result Execution time Memory
1017301 2024-07-09T07:17:32 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 348 ms 67964 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, LG = 18;
int q, n = 2, par[N][LG], sp[N][LG], h[N];
int sz = 1, nxt[N * 30][2];

void add(int x){
    int cur = 0;
    for (int i = 29; i >= 0; i --){
        bool b = (1 << i) & x;
        if (nxt[cur][b] == -1)
            nxt[cur][b] = sz++;
        cur = nxt[cur][b];
    }
}

int get(int x){
    int cur = 0;
    int res = 0;
    for (int i = 29; i >= 0; i --){
        bool b = (1 << i) & x;
        if (nxt[cur][!b] != -1){
            cur = nxt[cur][!b];
            res |= (1 << i);
        }
        else
            cur = nxt[cur][b];
    }
    return res;
}

int main(){
    memset(par, -1, sizeof par);
    memset(nxt, -1, sizeof nxt);

    cin >> q;
    while (q--){
        string s;
        cin >> s;

        if (s == "Add"){
            int x, y;
            cin >> x >> y;

            par[n][0] = x;
            sp[n][0] = y;

            for (int i = 1; i < LG; i ++){
                if (par[n][i - 1] == -1) continue;
                par[n][i] = par[par[n][i - 1]][i - 1];
                sp[n][i] = sp[n][i - 1] ^ sp[par[n][i - 1]][i - 1];
            }
            h[n] = h[x] + 1;

            int v = n;
            int d = h[v] - h[1];
            int val = 0;
            for (int i = 0; i < LG; i ++){
                if ((1 << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            add(val);
            // cout << "adding " << val << " in trie" << endl;

            n++;
        }
        else{
            int a, b;
            cin >> a >> b;

            int v = a;
            int d = h[v] - h[1];
            int val = 0;
            for (int i = 0; i < LG; i ++){
                if ((1 << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            // cout << "getting from " << val << endl; 
            cout << get(val) << endl;
        }
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 61532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 61532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 67964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 61532 KB Output isn't correct
2 Halted 0 ms 0 KB -