oj.uz

Submission #1017484

# Submission time Handle Problem Language Result Execution time Memory
1017484 2024-07-09T08:20:51 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 501 ms 190256 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

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

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

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);

    memset(par, -1, sizeof par);
    memset(nxt, -1, sizeof nxt);

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

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

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

            for (ll 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;

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

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

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

            ll v = a;
            ll d = h[v] - h[1];
            ll val = 0;
            for (ll i = 0; i < LG; i ++){
                if ((1ll << 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 59 ms 146004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 159568 KB Output is correct
2 Correct 501 ms 170324 KB Output is correct
3 Correct 467 ms 180088 KB Output is correct
4 Correct 378 ms 190076 KB Output is correct
5 Correct 416 ms 160412 KB Output is correct
6 Correct 384 ms 170324 KB Output is correct
7 Correct 346 ms 180284 KB Output is correct
8 Correct 335 ms 190256 KB Output is correct
9 Correct 384 ms 160336 KB Output is correct
10 Correct 415 ms 170580 KB Output is correct
11 Correct 373 ms 180344 KB Output is correct
12 Correct 301 ms 190084 KB Output is correct

Subtask #4
0 / 44.0

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