제출 #1180728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180728		sleepntsheep	Klasika (COCI20_klasika)	C++17	0 / 110	265 ms	129052 KiB

klasika

#include<stdio.h>
#define N 200055

int nq,n,hd[N],fa[N],nxt[N+N],vv_[N+N],ii,jj=1,dfn[N],out[N],dfc,ii_,dp[N],ww[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){
    dp[u]=dp[p]^ww[u];
    dfn[u]=dfc++;
    for(int j=hd[u];j;j=nxt[j])if(vv_[j]-p)dfs(vv_[j],u);
    out[u]=dfc-1;
}

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

struct{int lc,rc;}trie[N*400];
int tt[N*4],ll[99],rr[99],vv[99],oo;
void trieins(int&v,int val,int i){
    if(!v)v=++ii_;
    if(i==-1)return;
    trieins((val>>i)%2?trie[v].rc:trie[v].lc,val,i-1);
}

int trieqry(int val,int i){
    if(i==-1)return 0;
    int want=((val>>i)&1)^1,cnt=0;
    for(int i=0;i<oo;++i)cnt+=want?!!trie[vv[i]].rc:!!trie[vv[i]].lc;
    if(!cnt){
	for(int i=0;i<oo;++i)vv[i]=want?trie[vv[i]].lc:trie[vv[i]].rc;
	return trieqry(val,i-1);
    }else{
	for(int i=0;i<oo;++i)vv[i]=want?trie[vv[i]].rc:trie[vv[i]].lc;
	return (1<<i)+trieqry(val,i-1);
    }
}

void stins(int v,int l,int r,int p,int k){
    trieins(tt[v],k,29);
    if(l==r)return;
    if(p<=(l+r)/2)stins(v*2+1,l,(l+r)/2,p,k);
    else stins(v*2+2,(l+r)/2+1,r,p,k);
}
void gen(int v,int l,int r,int x,int y){
    if(r<x||y<l)return;
    if(x<=l&&r<=y){ 
	//printf(" Gen(%d %d %d)\n",v,l,r);
	vv[oo++]=tt[v];return; }
    gen(v*2+1,l,(l+r)/2,x,y);gen(v*2+2,(l+r)/2+1,r,x,y);
}

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;
	    Lnk(fa[jj],jj);ww[jj]=q[i].b;
	    q[i].a=jj;
	}
    }
    n=jj;
    dfs(1,1);
    for(int i=0;i<nq;++i){
	if(q[i].op[0]=='A'){
	    //printf(" Turn on %d at %d\n",dp[q[i].a],dfn[q[i].a]);
	    stins(0,0,n-1,dfn[q[i].a],dp[q[i].a]);
	}else{
	    oo=0;gen(0,0,n-1,dfn[q[i].b],out[q[i].b]);
	    //printf(" Qry %d on %d %d\n",dp[q[i].a],dfn[q[i].b],out[q[i].b]);
	    printf("%d\n",trieqry(dp[q[i].a],29));
	}

    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

klasika.cpp: In function 'int main()':
klasika.cpp:53:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[5]' [-Wformat=]
   53 |         scanf("%s%d%d",&q[i].op,&q[i].a,&q[i].b);
      |                ~^      ~~~~~~~~
      |                 |      |
      |                 char*  char (*)[5]
klasika.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d",&nq);
      |     ~~~~~^~~~~~~~~~
klasika.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%s%d%d",&q[i].op,&q[i].a,&q[i].b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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