Submission #1228017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228017		mnnit_prakharg	Klasika (COCI20_klasika)	C++20	33 / 110	341 ms	76400 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};
    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;
}

vector<ll> solve()
{
    int q;
    cin >> q;
    vector<ll> ansa;
    unordered_map<int, ll> mp;
    mp[1] = 0;
    Trie t;
    {
        Node* nd = t.head;
        for(int i = 0; i < maxl; i++){
            nd -> a[0] = new Node();
            nd = nd -> a[0];
        }
    }
    int sz = 1;
    for(int i = 0; i < q; i++){
        string ty;
        cin >> ty;
        if(ty == "Add"){
            int x;
            ll y;
            cin >> x >> y;
            sz++;
            mp[sz] = mp[x] ^ y;
            string s = f(mp[sz]);
            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 = nd -> a[v];
            }
        } else{
            int x, y;
            cin >> x >> y;
            ll me = mp[x];
            string s = f(me);
            Node* nd = t.head;
            ll ot = 0;
            for(int j = 0; j < maxl; j++){
                int v = 1 - (s[j] - '0');
                if(nd -> a[v] != nullptr) {
                    nd = nd -> a[v];
                    ot += 1ll << (maxl - j - 1);
                } 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: 33 / 33
• Subtask 4: 0 / 44