Submission #1180771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180771		sleepntsheep	Klasika (COCI20_klasika)	C++17	110 / 110	1421 ms	43680 KiB

klasika

#include<stdio.h>
#include<algorithm>
#define N 200055
#define B 2500

int nq,n,hd[N],fa[N],nxt[N+N],vv_[N+N],ii,jj=1,dfn[N],out[N],dfc,ii_,dp[N],dq[N];
void Lnk(int u,int v){int i=++ii;nxt[i]=hd[u];vv_[i]=v;hd[u]=i;}
void dfs(int u,int p){
    dq[dfc]=-1;
    dfn[u]=dfc++;
    for(int j=hd[u];j;j=nxt[j])if(vv_[j]-p)dfs(vv_[j],u);
    out[u]=dfc;
}

struct QQ{char op[5];int a,b;}q[N];

int rt[3000];
struct{int c[2];}trie[N*400];
void trieins(int&v,int val,int i){
    if(!v)v=++ii_;
    if(i==-1)return;
    trieins(trie[v].c[(val>>i)&1],val,i-1);
}

int trieqry(int t,int val,int i){
    if(i==-1)return 0;
    int want=((val>>i)&1)^1,cnt=0;
    if(!trie[t].c[((val>>i)&1)^1])
	return trieqry(trie[t].c[(val>>i)&1],val,i-1);
    else
	return (1<<i)^trieqry(trie[t].c[(val>>i)&1^1],val,i-1);
}

int main(){
    scanf("%d",&nq);
    for(int i=0;i<nq;++i){
	scanf("%s%d%d",q[i].op,&q[i].a,&q[i].b);
	if(q[i].op[0]=='A'){
	    fa[++jj]=q[i].a;
	    dp[jj]=dp[fa[jj]]^q[i].b;
	    Lnk(fa[jj],jj);
	    q[i].a=jj;
	}
    }
    n=jj;
    dfs(1,1);
    trieins(rt[0],0,30);
    dq[0]=0;
    for(int now=1,i=0;i<nq;++i){
	if(q[i].op[0]=='A'){
	    ++now;
	    trieins(rt[dfn[now]/B],dp[now],30);
	    dq[dfn[now]]=dp[now];
	}else{
	    int z=0,aa=dfn[q[i].b],bb=out[q[i].b]-1,sb=aa/B+1,eb=bb/B,da=dp[q[i].a];
	    auto C=[&](int i){ if(dq[i]!=-1&&(dq[i]^da)>z)z=da^dq[i]; };
	    if(sb<=eb){
		for(int i=sb;i<eb;++i) z=std::max(z,trieqry(rt[i],da,30));
		for(int i=aa;i<sb*B;++i)C(i);
		for(int i=eb*B;i<=bb;++i)C(i);
	    }else{
		for(int i=aa;i<=bb;++i)C(i);
	    }
	    printf("%d\n",z);
	}
    }

    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d",&nq);
      |     ~~~~~^~~~~~~~~~
klasika.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%s%d%d",q[i].op,&q[i].a,&q[i].b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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