oj.uz

Submission #1087809

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

using namespace std;

#define ii pair <int, int>
#define query pair <string, ii>
const int N = 2e5 + 10;
const int LG = 30;

int q, a, b, n = 1, child[N];
string s;
query queries[N];
vector <ii> v[N];

int XOR[N], tin[N], tout[N], timeDFS;
void dfs(int s) {
    tin[s] = ++timeDFS;
    for (ii z: v[s]) {
        XOR[z.first] = (XOR[s] ^ z.second);
        dfs(z.first);
    }
    tout[s] = timeDFS;
}

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 a) {
        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(tin[a]);
        }
    }

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

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

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

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

        return ans;
    }
} T;

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

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> s >> a >> b;
        queries[i] = query(s, ii(a, b));

        if (s[0] == 'A') {
            v[a].push_back(ii(++n, b));
            child[i] = n;
        }
    }

    dfs(1);

    for (int i = 1; i <= q; ++i) {
        if (queries[i].first[0] == 'Q') {
            cout << T.solve(XOR[queries[i].second.first], queries[i].second.second) << "\n";
        } else {
            T.add_num(XOR[child[i]], child[i]);
        }
    }

    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13148 KB Output is correct
2 Incorrect 4 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 4 ms 13148 KB Output is correct
2 Incorrect 4 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 471 ms 126084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

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