제출 #1161885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161885		ahmedhali107	Klasika (COCI20_klasika)	C++20	33 / 110	810 ms	589824 KiB

klasika

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;

const char nl = '\n';

template<class T, int bits>
struct xortrie {
    vector<array<int, 2>> trie = {{0, 0}};

    xortrie() {}

    void update(T val, int delta) {
        int node = 0;
        for (int i = bits - 1; i >= 0; i--) {
            int j = (val & (1 << i) ? 1 : 0);
            if (trie[node][j] == 0) {
                trie[node][j] = trie.size();
                trie.push_back({0, 0});
            }
            node = trie[node][j];
        }
    }

    void insert(T val) {
        update(val, 1);
    }

    T max(T val) {
        T ans = 0;
        int node = 0;
        if (!trie[0][0] && !trie[0][1]) return 0;
        for (int i = bits - 1; i >= 0; i--) {
            int j = (val & (1 << i) ? 0 : 1);
            if (trie[node][j]) {
                ans |= (1ll << i);
                node = trie[node][j];
            } else {
                node = trie[node][j ^ 1];
            }
        }
        return ans;
    }
};

struct segTree {
    int N;
    vector<xortrie<int, 30>> sg;

    segTree(int n) {
        N = 1;
        while (N < n) N <<= 1;
        sg.assign(N << 1, {});
    }

    void update(int i, int x) {
        for (i += N; i; i >>= 1) {
            sg[i].insert(x);
        }
    }

    int query(int l, int r, int x) {
        int ans = 0;
        for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) ans = max(ans, sg[l++].max(x));
            if (r % 2 == 0) ans = max(ans, sg[r--].max(x));
        }
        return ans;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(1);
    vector<int> a(1);
    vector<array<int, 3>> qs(n);
    for (int i = 0; i < n; i++) {
        string t;
        cin >> t;
        if (t == "Add") {
            int u, x;
            cin >> u >> x, --u;
            g[u].push_back(g.size());
            a.push_back(a[u] ^ x);
            qs[i] = {1, (int) g.size(), 0};
            g.emplace_back();
        } else {
            int u, v;
            cin >> u >> v, --u, --v;
            qs[i] = {2, u, v};
        }
    }
    int timer = -1;
    vector<int> tin(n), tout(n);
    auto dfs = [&](auto &&dfs, int u) -> void {
        tin[u] = ++timer;
        for (int v: g[u]) dfs(dfs, v);
        tout[u] = timer;
    };
    dfs(dfs, 0);
    segTree sg(n);
    sg.update(0, 0);
    for (auto &[t, u, v]: qs) {
        if (t == 1) {
            sg.update(tin[u], a[u]);
        } else {
            cout << sg.query(tin[v], tout[v], a[u]) << nl;
        }
    }
}

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

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44