結果

問題 No.1790 Subtree Deletion
ユーザー tailstails
提出日時 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

ソースコード

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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0