結果

問題 No.1790 Subtree Deletion
ユーザー tailstails
提出日時 2021-12-19 06:32:34
言語 cLay
(20241019-1)
結果
AC  
実行時間 60 ms / 3,000 ms
コード長 1,016 bytes
コンパイル時間 3,239 ms
コンパイル使用メモリ 179,140 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2024-09-15 14:25:30
合計ジャッジ時間 4,860 ms
ジャッジサーバーID
(参考情報)
judge2 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

wgraph<ull> g;
ull na[1d5+1];
struct{int l,r;}lr[1d5+1];
int f(int i,int p,int x){
lr[i].l=x++;
REP(j,g.es[i]){
int k=g.edge[i][j];
if(k!=p){
x=f(k,i,x);
}else{
na[lr[i].l]=g.cost[i][j];
}
}
lr[i].r=x;
return x;
}
int l[1d5],r[];
ull a[];
struct segt {
ull a;
int d,e;
};
inline
segt segtree_ph_func(segt a,segt b){
segt r;
int d=a.d-b.e;
r.d=(d>=0?d:0)+b.d;
r.e=(d>=0?0:-d)+a.e;
r.a=(d>=0?a.a:0)^(d<=0?b.a:0);
return r;
}
{
ll@n;
rd((l,r,a)(n-1));
g.setEdge(n+1,n-1,l,r,a);
f(1,0,1);
segtree_ph<segt> t;
t.walloc(n+2,1);
t[0]=segt{0,0,0};
t[n+1]=segt{0,0,0};
rep(i,1,n+1){
t[i]=segt{na[i],0,0};
}
t.build();
ll@q;
rep(q){
ll@w,@x;
if(w==1){
{
int i=lr[x].l-1;
segt s=t[i];
s.d+=1;
t.change(i,s);
}
{
int i=lr[x].r;
segt s=t[i];
s.e+=1;
t.change(i,s);
}
}
if(w==2){
ull z=0;
segt s1=t.get(0,lr[x].l);
if(s1.d<=t[lr[x].l].e){
segt s2=t.get(0,lr[x].r);
z=s1.a^s2.a^na[lr[x].l];
}
wt(z);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0