結果

問題 No.1790 Subtree Deletion
ユーザー tailstails
提出日時 2021-12-22 12:43:20
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 24 ms / 3,000 ms
コード長 2,372 bytes
コンパイル時間 1,461 ms
コンパイル使用メモリ 33,908 KB
実行使用メモリ 15,184 KB
最終ジャッジ日時 2023-10-14 11:00:36
合計ジャッジ時間 3,031 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,648 KB
testcase_01 AC 2 ms
7,712 KB
testcase_02 AC 1 ms
7,628 KB
testcase_03 AC 20 ms
13,288 KB
testcase_04 AC 19 ms
13,272 KB
testcase_05 AC 19 ms
13,432 KB
testcase_06 AC 19 ms
13,416 KB
testcase_07 AC 19 ms
13,328 KB
testcase_08 AC 3 ms
7,928 KB
testcase_09 AC 22 ms
15,080 KB
testcase_10 AC 24 ms
15,124 KB
testcase_11 AC 23 ms
15,184 KB
testcase_12 AC 18 ms
14,596 KB
testcase_13 AC 19 ms
14,188 KB
testcase_14 AC 7 ms
11,124 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:117:1: 警告: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int]
  117 | main(){
      | ^~~~
main.c: 関数 ‘main’ 内:
main.c:143:9: 警告: 関数 ‘write’ の暗黙的な宣言です [-Wimplicit-function-declaration]
  143 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:144:9: 警告: 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