結果

問題 No.1790 Subtree Deletion
コンテスト
ユーザー tails
提出日時 2021-12-22 12:33:04
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 30 ms / 3,000 ms
コード長 2,266 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 34,176 KB
実行使用メモリ 15,076 KB
最終ジャッジ日時 2024-09-16 05:40:29
合計ジャッジ時間 2,985 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:109:1: warning: return type defaults to 'int' [-Wimplicit-int]
  109 | main(){
      | ^~~~
main.c: In function 'main':
main.c:134:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  134 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:135:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
  135 |         _exit(0);
      |         ^~~~~
      |         _Exit

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char*mmap();
char wbuf[1<<25];

#define rd_skip() while(*rp++>=48)
#define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}
#define WTHI(v) {ulong _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(ulong*)wp=_d;wp+=_n;}
#define WTLO(v) {ulong _z=v,_n=8,_d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(ulong*)wp=_d;wp+=8;}
#define wt(v) if(v>=100000000){if(v>=10000000000000000l){WTHI(v/10000000000000000l);WTLO(v/100000000);}else WTHI(v/100000000);WTLO(v);}else{WTHI(v);}

#define rep(v,e) for(long v=0;v<e;++v)

typedef unsigned long ulong;

// fenwick

#define FWSIZE (1<<17)
ulong fw[FWSIZE];

static inline
void fw_add(int a,ulong v){
	while(fw[a]^=v,a)a-=a&-a;
}

static inline
ulong fw_get(int a){
	ulong z=0;
	while(z^=fw[a],a+=a&-a,a<FWSIZE);
	return z;
}

// graph

#define MAXV 100000
#define MAXE 100000
int en[MAXV+1];
int ei[MAXV+1];
int eb[MAXE<<1];
ulong ew[MAXE<<1];
int uv[MAXE<<1];
ulong uw[MAXE];

typedef struct{
	int alive;
	int p;
	int l,r;
	ulong a;
}nodet;

nodet nodes[MAXV+1];

int f(int i,int p,int x){
	nodes[i].l=x;
	++x;
	nodes[i].alive=1;
	nodes[i].p=p;
	rep(j,en[i]){
		long k=eb[ei[i]+j];
		if(k!=nodes[i].p){
			x=f(k,i,x);
		}else{
			nodes[i].a=ew[ei[i]+j];
		}
	}
	nodes[i].r=x;
	fw_add(nodes[i].l,nodes[i].a);
	return x;
}

void del(int i){
	if(nodes[i].alive){
		fw_add(nodes[i].l,nodes[i].a);
		nodes[i].alive=0;
		rep(j,en[i]){
			long k=eb[ei[i]+j];
			if(k!=nodes[i].p){
				del(k);
			}
		}
	}
}

char*graph_read(char*rp){
	rd(nv);
	for(long j=0;j<nv-1;++j){
		{ rd(t); uv[j<<1|0]=t; ++ei[t]; }
		{ rd(t); uv[j<<1|1]=t; ++ei[t]; }
		{ rd(t); uw[j]=t; }
	}
	{
		long s=0;
		for(long i=0;++i<=nv;){
			long t=s;
			s+=ei[i];
			ei[i]=t;
		}
	}
	for(long j=0;j<nv-1<<1;++j){
		long i=uv[j];
		long k=ei[i]+en[i]++;
		eb[k]=uv[j^1];
		ew[k]=uw[j>>1];
	}
	return rp;
}

main(){
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	char*wp=wbuf;
	rp=graph_read(rp);
	f(1,0,1);
	rd_skip();
	while(*rp){
		long w=*rp; rp+=2;
		rd(x);
		if(w=='1'){
			if(nodes[x].alive){
				del(x);
			}
		}
		if(w=='2'){
			ulong z=0;
			if(nodes[x].alive){
				z^=fw_get(nodes[x].l+1);
				z^=fw_get(nodes[x].r);
			}
			wt(z);
			*wp++='\n';
		}
	}

	write(1,wbuf,wp-wbuf);
	_exit(0);
}
0