Submission #348586

#	Time	Username	Problem	Language	Result	Execution time	Memory
348586		Nima_Naderi	Klasika (COCI20_klasika)	C++14	33 / 110	565 ms	191712 KiB

klasika

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

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 2e5 + 10;
const ll LOG = 30;
const ll MXM = MXN * LOG + 10;
const ll INF = 1e8;
ll cntr;
int L[MXM], R[MXM], mtm[MXM];
void Pak(ll u = 1, ll bit = LOG - 1){
    mtm[u] = INF;
    if(L[u]) Pak(L[u], bit - 1), L[u] = 0;
    if(R[u]) Pak(R[u], bit - 1), R[u] = 0;
}
void Add(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
    mtm[u] = min(1ll*mtm[u], tm);
    if(bit == -1) return;
    if((val >> bit) & 1LL){
        if(!R[u]) R[u] = cntr ++;
        Add(val, tm, R[u], bit - 1);
    }
    else{
        if(!L[u]) L[u] = cntr ++;
        Add(val, tm, L[u], bit - 1);
    }
}
ll GetMax(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
    if(bit == -1) return 0;
    if((val >> bit) & 1LL){
        if(L[u] && mtm[L[u]] <= tm) return GetMax(val, tm, L[u], bit - 1) + (1LL << bit);
        return GetMax(val, tm, R[u], bit - 1);
    }
    else{
        if(R[u] && mtm[R[u]] <= tm) return GetMax(val, tm, R[u], bit - 1) + (1LL << bit);
        return GetMax(val, tm, L[u], bit - 1);
    }
}
ll n = 1, q, x, y;
ll px[MXN], ANS[MXN];
ll sub[MXN], big[MXN];
vector<pll> adj[MXN];
vector<pair<pll, ll>> Qry, Q[MXN];
string s;
void prep(ll u, ll par){
    sub[u] = 1;
    for(auto Pr : adj[u]){
        ll v, w; tie(v, w) = Pr;
        if(v != par){
            px[v] = px[u] ^ w;
            prep(v, u);
            if(sub[v] > sub[big[u]]) big[u] = v;
            sub[u] += sub[v];
        }
    }
}
void dfs(ll u, ll par){
    Add(px[u], u);
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v != par) dfs(v, u);
    }
}
void DFS(ll u, ll par){
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v == par || v == big[u]) continue;
        DFS(v, u);
        Pak();
    }
    if(big[u]) DFS(big[u], u);
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v == par || v == big[u]) continue;
        dfs(v, u);
    }
    Add(px[u], u);
    for(auto Prr : Q[u]){
        ll val, tm, id = Prr.second;
        tie(val, tm) = Prr.first;
        ANS[id] = GetMax(val, tm);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cntr = 2;
    for(int i = 0; i < MXM; i ++) mtm[i] = INF;
    cin >> q;
    for(int i = 1; i <= q; i ++){
        cin >> s >> x >> y;
        if(s[0] == 'A'){
            ++ n;
            adj[x].push_back({n, y});
            adj[n].push_back({x, y});
        }
        else Qry.push_back({{x, y}, n});
    }
    prep(1, 0);
    for(int i = 0; i < int(Qry.size()); i ++){
        ll a, b, t = Qry[i].second; tie(a, b) = Qry[i].first;
        Q[b].push_back({{px[a], t}, i});
    }
    DFS(1, 0);
    for(int i = 0; i < int(Qry.size()); i ++) cout << ANS[i] << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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