Submission #336416

#	Time	Username	Problem	Language	Result	Execution time	Memory
336416		AriaH	Klasika (COCI20_klasika)	C++11	110 / 110	3182 ms	429432 KiB

klasika

/// well Fuck this problem Fuck this shitty problem if you are reading my code, dont solve this stupied problem!
/** I can do this all day **/

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

#define ll int
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair < ll, ll >             pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const ll N = 2e5 + 10;
const ll M = 16 * N;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const int LOG = 30;

string ver[N];

int n = 1, ptr = 0, Cnt = 1, q, a[N], b[N], w[N], St[N], Fi[N], child[M][2];

vector < int > G[N];

set < int > st[M];

void dfs(int v)
{
    St[v] = ++ptr;
    for(auto u : G[v])
    {
        dfs(u);
    }
    Fi[v] = ptr;
}
inline void add_trie(int x, int y)
{
    int node = 1;
    for(int T = 30; T >= 0; T--)
    {
        int rem = ((x & (1 << T)) > 0);
        if (child[node][rem] == 0) { child[node][rem] = ++ Cnt; }
        node = child[node][rem];
        st[node].insert(y);
    }
}
inline int ask_trie(int x, int B)
{
    int tl = St[B], tr = Fi[B], node = 1, tot = 0;
    for(int T = 30; T >= 0; T--)
    {
        int rem = ((x & (1 << T)) > 0), other = child[node][1 - rem], is_Ok = 1;
        auto it = st[other].lower_bound(tl);
        if(it == st[other].end() || (*it) > tr) is_Ok = 0;
        if(is_Ok) { tot = tot + (1 << T); node = other; }
	else { node = child[node][rem]; }
    }
    return tot;
}

int main(){
    fast_io;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> ver[i];
        if(ver[i] == "Add") { cin >> a[i] >> b[i]; n ++; w[n] = w[a[i]] ^ b[i]; G[a[i]].push_back(n); a[i] = n; }
	else { cin >> a[i] >> b[i]; }
    }
    dfs(1); add_trie(0, St[1]);
    /// for(int i = 1; i <= n; i ++) cout << St[i] << " " << Fi[i] << endl;
    for (int i = 1; i <= q; i++)
    {
        if(ver[i] == "Add") { add_trie(w[a[i]], St[a[i]]); }
	else { cout << ask_trie(w[a[i]], b[i]) << endl;}
    }
}
/*!
        stay away from negative people they have a problem for every solution !
*/
/*
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1 
*/

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