oj.uz

Submission #1087789

# Submission time Handle Problem Language Result Execution time Memory
1087789 2024-09-13T08:38:58 Z MinhKien Klasika (COCI20_klasika) C++17
0 / 110
 416 ms 129088 KB 
#include <iostream>
#include <string>
#include <vector>
#include <set>

#define int long long
using namespace std;

const int N = 2e5 + 10;
const int LG = 30;

int q, x[N];
int child[N];

vector <int> v[N];
int num[N], last[N], cnt, k = 1;
void dfs(int s) {
    num[s] = last[s] = ++cnt;

    for (int z: v[s]) {
        dfs(z);
    }
    last[s] = cnt;
}

struct Trie {
    struct node {
        node *child[2];
        set <int> s;

        node () {
            child[0] = child[1] = nullptr;
            s.clear();
        }
    };

    node *root;
    Trie () {
        root = new node ();
    }

    void add_num(int val, int Num) {
        node *cur = root;
        for (int i = LG; i >= 0; --i) {
            int c = val >> i & 1;
            if (cur->child[c] == nullptr) cur->child[c] = new node();
            cur = cur->child[c];
            cur->s.insert(Num);
        }
    }

    bool in(node *x, int l, int r) {
        set <int> :: iterator it = x->s.lower_bound(l);
        if (it == x->s.end() || *it > r) return false;
        return true;
    }

    int solve(int val, int b) {
        int ans = 0;
        node *cur = root;

        for (int i = LG; i >= 0; --i) {
            int c = (val >> i & 1) ^ 1;

            if (cur->child[c] != nullptr && in(cur->child[c], num[b], last[b])) {
                cur = cur->child[c];
                ans |= (1 << i);
            } else {
                if (cur->child[c ^ 1] != nullptr && in(cur->child[c ^ 1], num[b], last[b])) {
                    cur = cur->child[c ^ 1];
                } else {
                    return ans;
                }
            }
        }

        return ans;
    }
} T;

struct query {
    string t;
    int a, b;
} Q[N];

signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> q;
    k = 1;
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].t >> Q[i].a >> Q[i].b;

        if (Q[i].t == "Add") {
            v[Q[i].a].push_back(++k);
            child[i] = k;
        }
    }

    dfs(1);

    for (int i = 1; i <= q; ++i) {
        if (Q[i].t == "Add") {
            k = child[i];
            x[k] = x[Q[i].a] ^ Q[i].b;
            T.add_num(x[k], num[k]);
        } else {
            cout << T.solve(x[Q[i].a], Q[i].b) << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Incorrect 6 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Incorrect 6 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Incorrect 6 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -