oj.uz

Submission #1087748

# Submission time Handle Problem Language Result Execution time Memory
1087748 2024-09-13T07:45:11 Z MinhKien Klasika (COCI20_klasika) C++17
0 / 110
 411 ms 128544 KB 
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

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

int q, x[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] = last[z];
    }
}

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);
        }
    }

    int solve(int val, int b) {
        int ans = 0;
        node *cur = root;
        set <int> :: iterator it;

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

            bool check = false;
            if (cur->child[c] != nullptr) {
                it = cur->child[c]->s.lower_bound(num[b]);
                if (it != cur->child[c]->s.end() && *it <= last[b]) {
                    check = true;
                    ans |= (1 << i);
                    cur = cur->child[c];
                }
            }

            if (!check) {
                if (cur->child[c ^ 1] != nullptr) {
                    it = cur->child[c ^ 1]->s.lower_bound(num[b]);
                    if (it != cur->child[c ^ 1]->s.end() && *it <= last[b]) {
                        cur = cur->child[c ^ 1];
                        check = true;
                    }
                }
            }

            if (!check) return ans;
        }

        return ans;
    }
} T;

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

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

    cin >> q;
    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);
        }
    }

    dfs(1);

    k = 1;
    for (int i = 1; i <= q; ++i) {
        if (Q[i].t == "Add") {
            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 13148 KB Output is correct
2 Incorrect 6 ms 13148 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 13148 KB Output is correct
2 Incorrect 6 ms 13148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 411 ms 128544 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 13148 KB Output is correct
2 Incorrect 6 ms 13148 KB Output isn't correct
3 Halted 0 ms 0 KB -