#725043 (cLay) No.1790 Subtree Deletion

• 問題: No.1790 Subtree Deletion
• ユーザー: tails
• 提出日時: 2021-12-19 06:32:34
• 言語: cLay (20240714-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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	57 ms; 16,896 KB
testcase_04	AC	58 ms; 16,768 KB
testcase_05	AC	58 ms; 16,896 KB
testcase_06	AC	60 ms; 16,896 KB
testcase_07	AC	58 ms; 16,896 KB
testcase_08	AC	5 ms; 5,376 KB
testcase_09	AC	38 ms; 17,792 KB
testcase_10	AC	56 ms; 17,664 KB
testcase_11	AC	58 ms; 17,664 KB
testcase_12	AC	32 ms; 16,384 KB
testcase_13	AC	39 ms; 15,360 KB
testcase_14	AC	16 ms; 7,296 KB

ソースコード

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);
		}
	}
}