Submission #1117361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117361		Tai_xiu	Klasika (COCI20_klasika)	C++14	110 / 110	1699 ms	51016 KiB

klasika

#include<bits/stdc++.h>
using namespace std;

#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
const Z blocksize=2024;
Z tour[maxn],tin[maxn],tout[maxn],s[maxn],id=0,cnode=1,nv[maxn],check[maxn];
Z q;
vi g[maxn];
struct item
{
    Z type,x,y;
    item(){}
    item(Z _type,Z _x,Z _y)
    {
        type=_type;
        x=_x;
        y=_y;
    }
}Q[maxn];
Z tt[maxn*64][2];
struct trie
{
    Z root;

    void update(Z val)
    {
        Z curr=root;
        REP(i,30,0){
            if (val>>i&1){
                if (tt[curr][1]==0){
                    tt[curr][1]= ++cnode;
                }
                curr=tt[curr][1];
            }
            else{
               if (tt[curr][0]==0){
                    tt[curr][0]= ++cnode;
                }
                curr=tt[curr][0];
            }
        }
    }
    Z query (Z val)
    {
        Z curr=root;
        Z ans=0;
        REP(i,30,0){

            Z tam=(val>>i&1);
            if (tt[curr][tam^1]!=0){
                ans+=(1<<i);
                 curr=tt[curr][tam^1];
            }
            else if ( tt[curr][tam]!=0){
                 curr=tt[curr][tam];
            }
            else return ans;
        }
        return ans;
    }
}st[maxn];
void dfs(Z u)
{
    tour[++id]=u;
    tin[u]=id;
    for (Z v:g[u]){
        dfs(v);
    }
    tout[u]=id;
}
void update(Z pos,Z val)
{
  nv[pos]=val;
  check[pos]=1;
  st[pos/blocksize].update(val);
}
Z query(Z l,Z r,Z val)
{
   Z ans=0;
    Z taml=l/blocksize,tamr=r/blocksize;
    if (l/blocksize==r/blocksize){
        FOR(i,l,r){
            if (check[i])
                ans=max(ans,nv[i]^val);
        }
        return ans;
    }
    FOR(i,l,r){
        if (i%blocksize==0){
            taml=i/blocksize;
            break;
        }
        if (check[i]) ans=max(ans,nv[i]^val);
    }
    REP(i,r,l){
        if (check[i]) ans=max(ans,nv[i]^val);
        if (i%blocksize==0){
            tamr=(i-1)/blocksize;
            break;
        }
    }
    FOR(i,taml,tamr){
        ans=max(ans,st[i].query(val));
    }
    return ans;
}
void solve()
{
    cin>>q;
    Z cnt=1;
    FOR(i,1,q)
    {
        string aa;
        Z x,y,type;
        cin>>aa>>x>>y;
        if (aa[0]=='A') type=1;
        else type=2;
        if (type==1)
        {
            cnt++;
            g[x].pb(cnt);
            s[cnt]=(s[x]^y);
            Q[i]=item(1,cnt,0);
        }
        else{
            Q[i]=item(2,x,y);
        }
    }
    dfs(1);

    cnode=cnt/blocksize+1;
    FOR(i,1,cnt/blocksize+1) st[i].root=i;
    update(1,s[1]);
    FOR(i,1,q){
        if (Q[i].type==1){
            update(tin[Q[i].x],s[Q[i].x]);
        }
        else{
            Z tam=s[Q[i].x];
            cout<<query(tin[Q[i].y],tout[Q[i].y],tam)<<'\n';
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Z t=1;
  //  cin>>t;
    while(t--) solve();
}

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