結果
問題 | 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;};inlinesegt 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);}}}