Submission #1292676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292676		paronmanukyan	Klasika (COCI20_klasika)	C++20	0 / 110	104 ms	68764 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define V vector
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back

const int N = 200000 + 5;
const int BT = 31;

struct Node {
    int ch[2];
    int pass; // how many active entries pass through this node
    V<int> tins[2]; // tins for edges 0/1 from this node
    Node() { ch[0]=ch[1]=0; pass=0; }
};

V<Node> trie;
int root = 0;

int new_node() {
    trie.emplace_back();
    return (int)trie.size()-1;
}

void ensure_child(int cur, int bit) {
    if (!trie[cur].ch[bit]) {
        int id = new_node();
        trie[cur].ch[bit] = id;
    }
}

void insert_sorted_vec(V<int> &v, int x) {
    // insert x keeping v sorted
    auto it = lower_bound(v.begin(), v.end(), x);
    v.insert(it, x);
}

int gch(int cur, int b) { return trie[cur].ch[b]; }

int n_nodes = 1;
int st[N];
int tin[N], tout[N];
int tm_ = 1;
V<int> adj[N];

void dfs(int node) {
    tin[node] = tm_++; 
    for (int to : adj[node]) dfs(to);
    tout[node] = tm_++;
}

void add_to_trie(int x, int y) {
    int cur = root;
    for (int i = BT - 1; i >= 0; --i) {
        int cb = (x >> i) & 1;
        ensure_child(cur, cb);
        int nxt = trie[cur].ch[cb];
        trie[nxt].pass++; // child node pass count
        // store y in the parent's bucket for edge cb (like original code)
        // keep sorted by insertion
        insert_sorted_vec(trie[cur].tins[cb], y);
        cur = nxt;
    }
}

void del_from_trie(int x, int y) {
    // If you need deletions (original lazy used only cnt--),
    // we only decrement pass counts along path; we won't physically remove y from vectors
    int cur = root;
    for (int i = BT - 1; i >= 0; --i) {
        int cb = (x >> i) & 1;
        int nxt = trie[cur].ch[cb];
        if (!nxt) return; // nothing to do
        trie[nxt].pass--;
        cur = nxt;
    }
}

int get_xor_max_in_range(int x, int L, int R) {
    int cur = root;
    int ans = 0;
    for (int i = BT - 1; i >= 0; --i) {
        if (!cur) break;
        int cb = (x >> i) & 1;
        int want = cb ^ 1;
        int kid = trie[cur].ch[want];
        if (kid && trie[kid].pass > 0) {
            auto &vec = trie[cur].tins[want];
            auto it = lower_bound(vec.begin(), vec.end(), L);
            if (it != vec.end() && *it <= R) {
                ans |= (1 << i);
                cur = kid;
                continue;
            }
        }
        // else go to same bit child
        cur = trie[cur].ch[cb];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if 0
    // debug: turn off ios sync when not needed
#endif

    trie.reserve(1<<20); // reserve some space so push_backs don't reallocate too often
    trie.clear();
    root = new_node(); // root is 0

    add_to_trie(0, 1); // initial
    st[1] = 0;

    int q; 
    if (!(cin >> q)) return 0;
    V<pair<int,pii>> qr(q+1);

    // read all queries, build the tree of nodes (adj)
    int cur_n = 1;
    rep(i,1,q,1) {
        string s; int x,b;
        cin >> s >> x >> b;
        if (s[0] == 'A') {
            ++cur_n;
            st[cur_n] = st[x] ^ b;
            adj[x].pb(cur_n);
            qr[i] = {0, {cur_n, b}};
        } else {
            qr[i] = {1, {x, b}};
        }
    }

    // dfs once to compute tin/tout
    dfs(1);

    // Process queries in order: for 'A' do add (with tin known), for query do get
    rep(i,1,q,1) {
        if (qr[i].ff == 0) {
            int node = qr[i].ss.ff;
            add_to_trie(st[node], tin[node]);
        } else {
            int xnode = qr[i].ss.ff;
            int ynode = qr[i].ss.ss;
            cout << get_xor_max_in_range(st[xnode], tin[ynode], tout[ynode]) << '\n';
        }
    }

    return 0;
}

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