oj.uz

Submission #784105

# Submission time Handle Problem Language Result Execution time Memory
784105 2023-07-15T16:49:52 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
100 / 100
 1602 ms 262248 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=200000+10,maxm=500000+10;
vector<int>adj[maxn];
int par[maxn],val[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<int,int>stf[maxn];
int kaf=(1<<19);
 
struct cmp {
    bool operator() (int a, int b) const {
        return high[a]<high[b];
    }
};

struct segment{
	set<int,cmp>seg[(1<<20)];
	int get(int i){
		if(i==0){
			return 0;
		}
		if((int)seg[i].size()==0){
			return get((i>>1));
		}
		auto x=*seg[i].rbegin();
		int z=get((i>>1));
		if(high[z]>high[x]){
			return z;
		}
		else{
			return x;
		}
	}
	void del(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].erase(w);
			return ;
		}
		int m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}
 
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].insert(w);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
}segbal;
 
struct segjam{
	int seg[(1<<20)];
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		int ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(int i,int w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		upd((i>>1),w);
	}
}segjam,segted;
 
struct segres{
	int seg[(1<<20)];
	segres(){
		for(int i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(int i=1;i<kaf;i++){
			seg[i]=-1;
		}
	}
	void calc(int i){
		if(seg[(i<<1)]==-1&&seg[(i<<1)^1]==-1){
			seg[i]=-1;
			return ;
		}
		if(seg[(i<<1)]==-1){
			seg[i]=seg[(i<<1)^1];
			return ;
		}
		if(seg[(i<<1)^1]==-1){
			seg[i]=seg[(i<<1)];
			return ;
		}
		seg[i]=1ll*seg[(i<<1)^1]*seg[(i<<1)]%mod;
		return ;
	}
 
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
 
}res;
 
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
 
void aval(){	
	for(int i=0;i<maxn;i++){
		val[i]=-1;
	}
	fact[0]=1;
	for(int i=1;i<maxm;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
	for(int i=maxm-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
 
inline int c(int i,int j){
	if(i<0||j<0||i<j){
		return 0;
	}
	int ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}
 
void dfs(int u,int para=0){
	cnt[u]=1;
	high[u]=high[para]+1;
	timea++;
	stf[u].first=timea;
	par[u]=para;
	for(auto x:adj[u]){
		if(x!=para){
			dfs(x,u);
			cnt[u]+=cnt[x];
		}
	}
	stf[u].second=timea;
}
 
inline int hes(int a,int b){
	a++;
	int ret=c(b+a-1,a-1);	
	return ret;
}
 
void upd(int u,int w){
	val[u]=w;
	int pp=segbal.get(stf[u].first+kaf);
	int jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	int ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	segted.upd(kaf+stf[u].first,ted);
	segted.upd(kaf+stf[pp].first,-ted);
	segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,-jam+w);
	segjam.upd(kaf+stf[pp].first,+jam-w);
	int jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int fake=hes(tedp-1,val[pp]-jamp);
	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	fake=hes(ted-1,val[u]-jam);
	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,fake);
}
 
void del(int u){
	int pp=segbal.get(stf[u].first+kaf);
	int jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	int ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	segted.upd(kaf+stf[u].first,-ted);
	segted.upd(kaf+stf[pp].first,+ted);
	segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,+jam-val[u]);
	segjam.upd(kaf+stf[pp].first,-jam+val[u]);
	val[u]=-1;
	int jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int fake=hes(tedp-1,val[pp]-jamp);
	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,-1);
}
void tof(){
	res.upd(1,0,kaf-1,stf[1].first,stf[1].first,hes(n-1,val[1]));
	segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	val[1]=k;
	tof();
	int q;
	cin>>q;
	asd=1;
	cout<<res.seg[1]<<"\n";
	for(;asd<=q;asd++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			int u;
			cin>>u;
			del(u);
		}
		cout<<res.seg[1]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 81064 KB Output is correct
2 Correct 121 ms 81036 KB Output is correct
3 Correct 108 ms 81112 KB Output is correct
4 Correct 106 ms 81100 KB Output is correct
5 Correct 109 ms 77120 KB Output is correct
6 Correct 38 ms 63368 KB Output is correct
7 Correct 38 ms 63140 KB Output is correct
8 Correct 38 ms 63188 KB Output is correct
9 Correct 105 ms 73464 KB Output is correct
10 Correct 103 ms 73440 KB Output is correct
11 Correct 101 ms 73380 KB Output is correct
12 Correct 99 ms 72836 KB Output is correct
13 Correct 116 ms 80064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63116 KB Output is correct
2 Correct 37 ms 63108 KB Output is correct
3 Correct 37 ms 63148 KB Output is correct
4 Correct 40 ms 63180 KB Output is correct
5 Correct 40 ms 63148 KB Output is correct
6 Correct 41 ms 63308 KB Output is correct
7 Correct 42 ms 63256 KB Output is correct
8 Correct 41 ms 63344 KB Output is correct
9 Correct 49 ms 63392 KB Output is correct
10 Correct 47 ms 63480 KB Output is correct
11 Correct 44 ms 63632 KB Output is correct
12 Correct 38 ms 63468 KB Output is correct
13 Correct 44 ms 63576 KB Output is correct
14 Correct 44 ms 63568 KB Output is correct
15 Correct 46 ms 63828 KB Output is correct
16 Correct 41 ms 63440 KB Output is correct
17 Correct 43 ms 63564 KB Output is correct
18 Correct 45 ms 63492 KB Output is correct
19 Correct 48 ms 63436 KB Output is correct
20 Correct 45 ms 63348 KB Output is correct
21 Correct 45 ms 63320 KB Output is correct
22 Correct 38 ms 63184 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 86036 KB Output is correct
2 Correct 210 ms 91308 KB Output is correct
3 Correct 143 ms 87088 KB Output is correct
4 Correct 286 ms 100332 KB Output is correct
5 Correct 891 ms 144632 KB Output is correct
6 Correct 42 ms 64076 KB Output is correct
7 Correct 39 ms 63372 KB Output is correct
8 Correct 40 ms 63592 KB Output is correct
9 Correct 338 ms 83132 KB Output is correct
10 Correct 270 ms 81544 KB Output is correct
11 Correct 262 ms 81108 KB Output is correct
12 Correct 377 ms 81492 KB Output is correct
13 Correct 1247 ms 224736 KB Output is correct
14 Correct 1135 ms 215308 KB Output is correct
15 Correct 1602 ms 262248 KB Output is correct
16 Correct 1497 ms 253004 KB Output is correct
17 Correct 1114 ms 215332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 78656 KB Output is correct
2 Correct 559 ms 78624 KB Output is correct
3 Correct 520 ms 78572 KB Output is correct
4 Correct 456 ms 78668 KB Output is correct
5 Correct 444 ms 77852 KB Output is correct
6 Correct 475 ms 78668 KB Output is correct
7 Correct 374 ms 71872 KB Output is correct
8 Correct 393 ms 71948 KB Output is correct
9 Correct 478 ms 78720 KB Output is correct
10 Correct 466 ms 78632 KB Output is correct
11 Correct 446 ms 78672 KB Output is correct
12 Correct 386 ms 71856 KB Output is correct
13 Correct 350 ms 69316 KB Output is correct
14 Correct 317 ms 70248 KB Output is correct
15 Correct 347 ms 70372 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 81064 KB Output is correct
2 Correct 121 ms 81036 KB Output is correct
3 Correct 108 ms 81112 KB Output is correct
4 Correct 106 ms 81100 KB Output is correct
5 Correct 109 ms 77120 KB Output is correct
6 Correct 38 ms 63368 KB Output is correct
7 Correct 38 ms 63140 KB Output is correct
8 Correct 38 ms 63188 KB Output is correct
9 Correct 105 ms 73464 KB Output is correct
10 Correct 103 ms 73440 KB Output is correct
11 Correct 101 ms 73380 KB Output is correct
12 Correct 99 ms 72836 KB Output is correct
13 Correct 116 ms 80064 KB Output is correct
14 Correct 36 ms 63116 KB Output is correct
15 Correct 37 ms 63108 KB Output is correct
16 Correct 37 ms 63148 KB Output is correct
17 Correct 40 ms 63180 KB Output is correct
18 Correct 40 ms 63148 KB Output is correct
19 Correct 41 ms 63308 KB Output is correct
20 Correct 42 ms 63256 KB Output is correct
21 Correct 41 ms 63344 KB Output is correct
22 Correct 49 ms 63392 KB Output is correct
23 Correct 47 ms 63480 KB Output is correct
24 Correct 44 ms 63632 KB Output is correct
25 Correct 38 ms 63468 KB Output is correct
26 Correct 44 ms 63576 KB Output is correct
27 Correct 44 ms 63568 KB Output is correct
28 Correct 46 ms 63828 KB Output is correct
29 Correct 41 ms 63440 KB Output is correct
30 Correct 43 ms 63564 KB Output is correct
31 Correct 45 ms 63492 KB Output is correct
32 Correct 48 ms 63436 KB Output is correct
33 Correct 45 ms 63348 KB Output is correct
34 Correct 45 ms 63320 KB Output is correct
35 Correct 38 ms 63184 KB Output is correct
36 Correct 155 ms 86036 KB Output is correct
37 Correct 210 ms 91308 KB Output is correct
38 Correct 143 ms 87088 KB Output is correct
39 Correct 286 ms 100332 KB Output is correct
40 Correct 891 ms 144632 KB Output is correct
41 Correct 42 ms 64076 KB Output is correct
42 Correct 39 ms 63372 KB Output is correct
43 Correct 40 ms 63592 KB Output is correct
44 Correct 338 ms 83132 KB Output is correct
45 Correct 270 ms 81544 KB Output is correct
46 Correct 262 ms 81108 KB Output is correct
47 Correct 377 ms 81492 KB Output is correct
48 Correct 1247 ms 224736 KB Output is correct
49 Correct 1135 ms 215308 KB Output is correct
50 Correct 1602 ms 262248 KB Output is correct
51 Correct 1497 ms 253004 KB Output is correct
52 Correct 1114 ms 215332 KB Output is correct
53 Correct 522 ms 78656 KB Output is correct
54 Correct 559 ms 78624 KB Output is correct
55 Correct 520 ms 78572 KB Output is correct
56 Correct 456 ms 78668 KB Output is correct
57 Correct 444 ms 77852 KB Output is correct
58 Correct 475 ms 78668 KB Output is correct
59 Correct 374 ms 71872 KB Output is correct
60 Correct 393 ms 71948 KB Output is correct
61 Correct 478 ms 78720 KB Output is correct
62 Correct 466 ms 78632 KB Output is correct
63 Correct 446 ms 78672 KB Output is correct
64 Correct 386 ms 71856 KB Output is correct
65 Correct 350 ms 69316 KB Output is correct
66 Correct 317 ms 70248 KB Output is correct
67 Correct 347 ms 70372 KB Output is correct
68 Correct 36 ms 63120 KB Output is correct
69 Correct 39 ms 63136 KB Output is correct
70 Correct 521 ms 86364 KB Output is correct
71 Correct 575 ms 86292 KB Output is correct
72 Correct 542 ms 86280 KB Output is correct
73 Correct 528 ms 86332 KB Output is correct
74 Correct 681 ms 86716 KB Output is correct
75 Correct 606 ms 82344 KB Output is correct
76 Correct 449 ms 78632 KB Output is correct
77 Correct 495 ms 79156 KB Output is correct
78 Correct 553 ms 80180 KB Output is correct
79 Correct 527 ms 82468 KB Output is correct
80 Correct 629 ms 82208 KB Output is correct
81 Correct 667 ms 82656 KB Output is correct
82 Correct 350 ms 75812 KB Output is correct
83 Correct 359 ms 82836 KB Output is correct
84 Correct 418 ms 82148 KB Output is correct
85 Correct 379 ms 82316 KB Output is correct