結果
問題 | No.1790 Subtree Deletion |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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); } } }