Submission #1247521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247521		dfhdfhdsf	Klasika (COCI20_klasika)	C++20	0 / 110	692 ms	558416 KiB

klasika

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int TRIE_DEPTH = 31;
const int MAXN = 200000;

struct TrieNode {
    TrieNode* child[2];
    TrieNode() {
        child[0] = child[1] = nullptr;
    }
};

void trie_insert(TrieNode* root, int num) {
    TrieNode* cur = root;
    for (int i = TRIE_DEPTH - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!cur->child[bit]) {
            cur->child[bit] = new TrieNode();
        }
        cur = cur->child[bit];
    }
}

int trie_query(TrieNode* root, int num) {
    if (root == nullptr) return 0;
    TrieNode* cur = root;
    int res = 0;
    for (int i = TRIE_DEPTH - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int target_bit = 1 - bit;
        if (cur->child[target_bit]) {
            res |= (1 << i);
            cur = cur->child[target_bit];
        } else if (cur->child[bit]) {
            cur = cur->child[bit];
        } else {
            break;
        }
    }
    return res;
}

void destroy_trie(TrieNode* root) {
    if (root == nullptr) return;
    destroy_trie(root->child[0]);
    destroy_trie(root->child[1]);
    delete root;
}

struct SegmentTreeNode {
    TrieNode* trie;
    int l, r;
    SegmentTreeNode *left, *right;
    SegmentTreeNode(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {
        trie = new TrieNode();
    }
};

void update_seg_tree(SegmentTreeNode* root, int idx, int value) {
    if (root == nullptr) return;
    trie_insert(root->trie, value);
    if (root->l == root->r) {
        return;
    }
    int mid = (root->l + root->r) / 2;
    if (idx <= mid) {
        if (root->left == nullptr) {
            root->left = new SegmentTreeNode(root->l, mid);
        }
        update_seg_tree(root->left, idx, value);
    } else {
        if (root->right == nullptr) {
            root->right = new SegmentTreeNode(mid + 1, root->r);
        }
        update_seg_tree(root->right, idx, value);
    }
}

int query_seg_tree(SegmentTreeNode* root, int ql, int qr, int value) {
    if (root == nullptr || qr < root->l || ql > root->r) {
        return 0;
    }
    if (ql <= root->l && root->r <= qr) {
        return trie_query(root->trie, value);
    }
    int mid = (root->l + root->r) / 2;
    int res = 0;
    if (ql <= mid) {
        res = max(res, query_seg_tree(root->left, ql, qr, value));
    }
    if (qr > mid) {
        res = max(res, query_seg_tree(root->right, ql, qr, value));
    }
    return res;
}

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

    int Q;
    cin >> Q;

    vector<long long> xorRoot(MAXN + 5, 0);
    vector<int> parent(MAXN + 5, 0);
    vector<int> inTime(MAXN + 5, -1);
    vector<int> maxInTime(MAXN + 5, -1);
    vector<int> next_node(MAXN + 5, 0);

    int node_count = 1;
    inTime[1] = 0;
    maxInTime[1] = 0;
    next_node[1] = 0;
    xorRoot[1] = 0;
    parent[1] = 0;

    int current_time = 1;

    int max_time = 0;

    SegmentTreeNode* seg_tree_root = new SegmentTreeNode(0, MAXN + Q);
    update_seg_tree(seg_tree_root, 0, 0);

    for (int i = 0; i < Q; i++) {
        string type;
        cin >> type;
        if (type == "Add") {
            int x, y;
            cin >> x >> y;
            node_count++;
            int v = node_count;
            parent[v] = x;
            xorRoot[v] = xorRoot[x] ^ y;
            inTime[v] = current_time;
            maxInTime[v] = current_time;
            next_node[v] = parent[v];

            int t = current_time;
            update_seg_tree(seg_tree_root, t, xorRoot[v]);

            int u = parent[v];
            while (u != 0 && maxInTime[u] < t) {
                maxInTime[u] = t;
                int next_temp = next_node[u];
                next_node[u] = next_node[next_node[u]];
                u = next_temp;
            }

            current_time++;
        } else if (type == "Query") {
            int a, b;
            cin >> a >> b;
            int l = inTime[b];
            int r = maxInTime[b];
            int ans = query_seg_tree(seg_tree_root, l, r, xorRoot[a]);
            cout << ans << '\n';
        }
    }

    return 0;
}

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