結果
問題 | No.1790 Subtree Deletion |
ユーザー | tails |
提出日時 | 2021-12-22 12:43:20 |
言語 | C (gcc 13.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
ソースコード
#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 inlinevoid fw_add(int a,ulong v){while(fw[a]^=v,a)a-=a&-a;}static inlineulong fw_get(int a){ulong z=0;while(z^=fw[a],a+=a&-a,a<FWSIZE);return z;}// graph#define MAXV 100000#define MAXE 100000int 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);}