結果

問題 No.1790 Subtree Deletion
ユーザー tailstails
提出日時 2021-12-22 12:43:20
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 23 ms / 3,000 ms
コード長 2,372 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 35,072 KB
実行使用メモリ 15,364 KB
最終ジャッジ日時 2024-09-16 05:52:54
合計ジャッジ時間 2,345 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,780 KB
testcase_01 AC 2 ms
7,524 KB
testcase_02 AC 2 ms
8,040 KB
testcase_03 AC 19 ms
14,344 KB
testcase_04 AC 19 ms
13,668 KB
testcase_05 AC 19 ms
13,288 KB
testcase_06 AC 18 ms
13,540 KB
testcase_07 AC 18 ms
13,540 KB
testcase_08 AC 3 ms
9,952 KB
testcase_09 AC 20 ms
15,364 KB
testcase_10 AC 22 ms
14,204 KB
testcase_11 AC 23 ms
13,924 KB
testcase_12 AC 18 ms
12,776 KB
testcase_13 AC 17 ms
13,860 KB
testcase_14 AC 8 ms
10,084 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:117:1: warning: return type defaults to 'int' [-Wimplicit-int]
  117 | main(){
      | ^~~~
main.c: In function 'main':
main.c:143:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  143 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:144:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
  144 |         _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];

void fw_build(){
	for(int a=FWSIZE;--a;){
		fw[a&a-1]^=fw[a];
	}
}

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[nodes[i].l]=nodes[i].a;
	return x;
}

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

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);
	fw_build();
	rd_skip();
	while(*rp){
		long w=*rp; rp+=2;
		rd(x);
		if(w=='1'){
			if(nodes[x].alive){
				fw_add(nodes[x].l,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