Submission #1292682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292682		paronmanukyan	Klasika (COCI20_klasika)	C++20	33 / 110	461 ms	221220 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 = 2e5 + 5, BT = 30;
int g[BT * N][2];
V<int> tn[BT * N][2];    
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;
        }

        tn[cur][cb].pb(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 (g[cur][odw])
        {
            auto &vec = tn[cur][odw];
            auto it = lower_bound(vec.begin(), vec.end(), l);
            if (it != vec.end() && *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);

    for (int i = 0; i <= vl; i++)
        for (int b = 0; b < 2; b++)
            sort(tn[i][b].begin(), tn[i][b].end());

    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: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 33 / 33
• Subtask 4: 0 / 44