Submission #336409

#	Time	Username	Problem	Language	Result	Execution time	Memory
336409		AriaH	Klasika (COCI20_klasika)	C++11	33 / 110	1185 ms	219372 KiB

klasika

/** I can do this all day **/

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

typedef long long                   ll;
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 ll inf = 8e18;
const int LOG = 30;

ll q, n = 1, ptr, Cnt = 1, w[N], St[N], Fi[N], child[N][2];

set < ll > st[M];

vector < ll > G[N];

pair < string, pll > Q[N];

void dfs(int v)
{
    St[v] = ++ptr;
    for(auto u : G[v])
    {
	dfs(u);
    }
    Fi[v] = ptr;
}

/// add trie -> x = w ash ta root, v = starting time rasi ke mikhai add bokoni

inline void add_trie(ll x, ll y)
{
    ll node = 1;
    for(int T = 30; ~T; T --)
    {
	ll rem = ((x & (1 << T)) != 0);
	if(child[node][rem] == 0) /// set nashode
	{
	    child[node][rem] = ++Cnt;
	}
	node = child[node][rem];
	st[node].insert(y);
    }
}

/// check v, node -> aya toye set trie v rasi hast ke toye sub node bashe ya na
/*
inline bool check(int v, int node)
{
    auto it = st[v].lower_bound(St[node]);
    if(it == st[v].end() || *it > Fi[node]) return 0;
    return 1;
}
*/
/// ask trie x, b -> maximum xor ke adadmoon = x, va toye sub v bashe

inline ll ask_trie(ll x, ll b)
{
    ll tl = St[b], tr = Fi[b];
    ll node = 1, tot = 0;
    for(ll T = 30; ~T; T --)
    {
	ll rem = ((x & (1ll << 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 += (1ll << T);
	    node = other;
	}
	else
	{
	    node = child[node][rem];
	}
    }
    return tot;
}

int main()
{
    cin >> q;
    for(int i = 1; i <= q; i ++)
    {
	string s;
	ll a, b;
	cin >> s >> a >> b;
	Q[i] = Mp(s, Mp(a, b));
	if(s == "Add")
	{
	    n ++;
	    w[n] = w[a] ^ b;
	    G[a].push_back(n);
	    Q[i].S.F = n;
	}
    }
    dfs(1);
    add_trie(0, St[1]);
    for(int i = 1; i <= q; i ++)
    {
	if(Q[i].F == "Add")
	{
	    add_trie(w[Q[i].S.F], St[Q[i].S.F]);
	}
	else
	{
	    cout << ask_trie(w[Q[i].S.F], Q[i].S.S) << endl;
	}
    }
    return 0;
}
/*!
        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: 0 / 33
• Subtask 4: 0 / 44