Submission #1292422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292422		paronmanukyan	Klasika (COCI20_klasika)	C++20	33 / 110	43 ms	62608 KiB

klasika

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
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 repl(a, b, c, d) for (int a = b; a >= c; a -= d) 
#define pii pair<int, int> 
#define ff first 
#define ss second 
#define all(x) x.begin(), x.end() 
#define pb push_back 
#define sz(x) (int(x.size()))

const int N = 2e4 + 5, BT = 31;
int g[BT * N][2];
set<int> tn[BT * N][2];
int cnt[BT * N];
int root = 0, vl = 0;
int n = 1;
int st[N];
int tin[N], tout[N];
int tm = 1;
V<int> adj[N];

void dfs(int node) {
    tin[node] = tm; ++tm;
    for (auto i : adj[node]) {
        dfs(i);
    }
    tout[node] = tm; ++tm;
}

void add(int x, int y)
{
    int cur = root;
    for (int i = BT - 1; i >= 0; i--)
    {
        int cb = (x >> i) & 1;
        if (!g[cur][cb])
        {
            g[cur][cb] = ++vl;
            cnt[g[cur][cb]] = 1;
        }
        else
        {
            cnt[g[cur][cb]]++;
        }
        tn[cur][cb].insert(y);
        cur = g[cur][cb];
    }
}

void del(int x, int y)
{
    int cur = root;
    for (int i = BT - 1; i >= 0; i--)
    {
        int cb = (x >> i) & 1;
        cnt[g[cur][cb]]--;
        tn[cur][cb].erase(y);
        cur = g[cur][cb];
    }
}

int get(int x, int l, int r)
{
    int cur = root;
    int ans = 0;
    for (int i = BT - 1; i >= 0; i--)
    {
        int cb = (x >> i) & 1;
        int odw = cb ^ 1;
        if (cnt[g[cur][odw]])
        {
            auto it = tn[cur][odw].lower_bound(l);
            if (it != tn[cur][odw].end()) {
                if (*it <= r) {
                    ans += (1 << i);
                    cur = g[cur][odw];
                    continue;
                }
            }
        }
        cur = g[cur][cb];
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    add(0, 1);
    st[1] = 0;
    int q; cin >> q;
    V<pair<int, pii>> qr(q + 1);
    rep(i, 1, q, 1) {
        string s; cin >> s;
        int x, b; cin >> x >> b;
        if (s[0] == 'A') {
            ++n;
            st[n] = st[x] ^ b;
            adj[x].pb(n);
            qr[i] = { 0, {n, b} };
        }
        else {
            qr[i] = { 1, {x, b} };
        }
    }
    dfs(1);
    rep(i, 1, q, 1) {
        if (qr[i].ff == 0) {
            add(st[qr[i].ss.ff], tin[qr[i].ss.ff]);
        }
        else {
            cout << get(st[qr[i].ss.ff], tin[qr[i].ss.ss], tout[qr[i].ss.ss]) << "\n";
        }
    }
}

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