Submission #1228214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228214		mnnit_prakharg	Klasika (COCI20_klasika)	C++20	0 / 110	29 ms	8000 KiB

klasika

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
#define pb push_back
#define ub upper_bound

struct Node
{
    Node *a[2] = {nullptr};
    set<int> sta[2];
    Node()
    {
    }
};

struct Trie
{
    Node *head;
    Trie()
    {
        head = new Node();
    }
};

const int maxl = 33;

string f(ll x)
{
    string ans = "";
    for (int i = 0; i < maxl; i++)
    {
        if (1ll << i & x)
            ans += '1';
        else
            ans += '0';
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

struct Query
{
    int ty;
    int x;
    ll y;
};

void f(int r, vector<vector<pair<int, ll>>>& g, int& ct, vector<int>& tin, vector<int>& tout, ll cxor, vector<ll>& xra){
    xra[r] = cxor;
    tin[r] = ct;
    ct++;
    for(auto& x: g[r]){
        f(x.first, g, ct, tin, tout, cxor ^ x.second, xra);
    }
    tout[r] = ct;
    ct++;
}

vector<ll> solve()
{
    int q;
    cin >> q;
    vector<ll> ansa;
    int n = 1;
    Query qa[q];
    for (int i = 0; i < q; i++)
    {
        string ty;
        cin >> ty;
        int x;
        ll w;
        cin >> x >> w;
        if (ty == "Add")
            n++;
        qa[i] = {ty == "Add" ? 1 : 0, x, w};
    }
    vector<ll> xra(n);
    vector<vector<pair<int, ll>>> g(n, vector<pair<int, ll>>());
    {
        int csz = 1;
        for (int i = 0; i < q; i++)
        {
            if (qa[i].ty)
            {
                g[qa[i].x - 1].pb({csz, qa[i].y});
                csz++;
            }
        }
    }
    Trie t;
    vector<int> tin(n);
    vector<int> tout(n);
    {
        int ct = 0;
        f(0, g, ct, tin, tout, 0, xra);
    }
    int csz = 1;
    for(int i = 0; i < q; i++){
        if(qa[i].ty){
            string s = f(xra[csz]);
            Node* nd = t.head;
            for(int i = 0; i < maxl; i++){
                int v = s[i] - '0';
                if(nd -> a[v] == nullptr) nd -> a[v] = new Node();
                nd -> sta[v].insert(tin[csz]);
                nd = nd -> a[v];
            }
            csz++;
        } else{
            ll me = xra[qa[i].x - 1];
            string s = f(me);
            ll ot = 0;
            Node* nd = t.head;
            int st = tin[qa[i].y - 1], et = tout[qa[i].y - 1];
            for(int j = 0; j < maxl; j++){
                int v = 1 - (s[j] - '0');
                auto it = nd -> sta[v].lower_bound(st);
                if(it != nd -> sta[v].end() && *it <= et){
                    ot += 1ll << (maxl - j - 1);
                    nd = nd -> a[v];
                } else nd = nd -> a[1 - v];
            }
            ansa.pb(ot);
        }
    }
    return ansa;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        vector<ll> ansa = solve();
        for (ll x : ansa)
            cout << x << " ";
    }
    return 0;
}

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