Submission #336442

#	Time	Username	Problem	Language	Result	Execution time	Memory
336442		ewwdsgfvsd	Klasika (COCI20_klasika)	C++17	33 / 110	629 ms	524292 KiB

klasika

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = long long int;
#define F first
#define S second
#define pb push_back
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=31,SQ=200;
const ll INF=1e18;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pair<pll,ll>, null_type,less<pair<pll,ll>>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
struct tr{
    vector<ll> nx[2];
    ll k;
    void add(ll x) {
        ll v = 0;
        for (ll i=LN-1;i>=0;i--) {
            ll y=bool(x&(1<<i));
            if(!nx[y][v]) nx[y][v] = k++;
            v = nx[y][v];
        }
    }
    ll get(ll x){
        ll res=0,v=0;
        if(k==1) return 0;
        for(ll i=LN-1; i>=0; i--){
            ll y=((x&(1<<i))!=0);
            y=1-y;
            if(nx[y][v]) v=nx[y][v],res+=(1<<i);
            else v=nx[1-y][v];
        }
        return res;
    }
};
tr f[4*N];
ll q,a[N],t=1,st[N],fn[N],g=2;
vector<pair<ll,pll>> qu;
vector<pll> adj[N];
void dfs(ll v){
    st[v]=t++;
    for(pll p :adj[v]) a[p.F]=a[v]^p.S,dfs(p.F);
    fn[v]=t;
}
void build(ll v, ll l, ll r) {
    f[v].k=1;
    f[v].nx[0].resize((r-l+2)*(LN-1),0);
    f[v].nx[1].resize((r-l+2)*(LN-1),0);
    if (r-l==1) return;
    ll m=(l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m,r);
}
void upd(ll v, ll l, ll r, ll p, ll x){
    f[v].add(x);
    //cout << l << ' ' << r << ' ' << f[v].get(0) << '\n';
    if(r-l==1) return;
    ll m=(l+r)/2;
    if(p<m) upd(v*2,l,m,p,x);
    else upd(v*2+1,m,r,p,x);
}
ll get(ll v, ll l, ll r, ll tl, ll tr, ll x){
    if(tl>=tr) return 0;
    if(l==tl && r==tr) return f[v].get(x);
    ll m=(l+r)/2;
    return max(get(v*2,l,m,tl,min(m,tr),x),get(v*2+1,m,r,max(m,tl),tr,x));
}
int main(){
    fast_io;
    cin >> q;
    for(ll i=0; i<q; i++){
        string s;
        ll c,x,y;
        cin >> s >> x >> y;
        if(s[0]=='A') c=0;
        else c=1;
        if(c==0){
            qu.pb({c,{x,g}});
            adj[x].pb({g++,y});
        }else qu.pb({c,{x,y}});
    }
    dfs(1);
    build(1,1,t);
    upd(1,1,t,st[1],a[1]);
    for(ll i=0; i<q; i++){
        ll x=qu[i].S.F,y=qu[i].S.S;
        if(qu[i].F==0){
            //cout << i << ' ' << y << '\n';
            upd(1,1,t,st[y],a[y]);
        }else{
            //cout << (a[x]^a[y]) << '\n';
            cout << get(1,1,t,st[y],fn[y],a[x]) << '\n';
        }
    }
    //cout << st[4] << ' ' << fn[4] << ' ' << st[5] << ' ' << fn[5] << '\n';
    return 0;
}

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