oj.uz

Submission #784045

# Submission time Handle Problem Language Result Execution time Memory
784045 2023-07-15T15:27:00 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 293052 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=2000000+10,maxm=5000000+10;
vector<long long>adj[maxn],child[maxn];
long long par[maxn],val[maxn],link[maxn],fres[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<long long,long long>stf[maxn];
 
long long kaf=(1<<19);
 
struct segment{
	set<pair<long long,long long>>seg[(1<<20)];
	pair<long long,long long> get(long long i){
		if(i==0){
			return make_pair(0,0);
		}
		if((long long)seg[i].size()==0){
			return get((i>>1));
		}
		auto x=*seg[i].rbegin();
		return max(get((i>>1)),x);
	}
	void del(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].erase(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}
 
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].insert(make_pair(high[w],w));
			return ;
		}
		long long 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{
	long long seg[(1<<20)];
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(long long i,long long w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		upd((i>>1),w);
	}
}segjam,segted;
 
struct segres{
	long long seg[(1<<20)];
	segres(){
		for(long long i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(long long 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,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			w%=mod;
			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++){
		fres[i]=-1;
		val[i]=-1;
	}
	fact[0]=1;
	for(long long i=1;i<maxm;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
	for(long long i=maxm-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
 
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}
 
void dfs(long long u,long long 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){
			child[u].push_back(x);
			dfs(x,u);
			cnt[u]+=cnt[x];
		}
	}
	stf[u].second=timea;
}
 
long long hes(long long a,long long b){
	a++;
	long long ret=c(b+a-1,a-1);	
	return ret;
}

int findp(int u,int av){
	if(u==av||val[u]==-1){
		return findp(par[u],av);
	}
	return u;
}

long long porsjam(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		ret+=val[u];
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsjam(x,av);
	}
	return ret;
}

long long porsted(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsted(x,av);
	}
	ret++;
	return ret;
}

void upd(long long u,long long w){
	wa[u]=w;
	val[u]=w;
//	long long pp=segbal.get(stf[u].first+kaf).second;
	long long pp=findp(u,u);
//	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long jam=porsjam(u,u);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long ted=porsted(u,u);
	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);
//	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long jamp=porsjam(pp,pp);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
	fres[stf[pp].first]=fake;
//	cout<<u<<" "<<pp<<" "<<jamp<<" "<<val[pp]<<" "<<tedp<<"\n";
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	fake=hes(ted-1,val[u]-jam);
	fres[stf[u].first]=fake;
//	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,fake);
}
 
void del(long long u){
//	long long pp=segbal.get(stf[u].first+kaf).second;
	long long pp=findp(u,u);
//	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long jam=porsjam(u,u);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long ted=porsted(u,u);
	val[u]=-1;
	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-wa[u]);
//	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long jamp=porsjam(pp,pp);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
	fres[stf[pp].first]=fake;
	fres[stf[u].first]=-1;
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,-1);
//	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);
//	val[u]=-1;
}
 
void calres(){
	long long ret=1;
	for(int i=stf[1].first;i<=stf[1].second;i++){
//		cout<<i<<" asd "<<fres[i]<<"\n";
		if(fres[i]==-1){
			continue;
		}
		ret*=fres[i];
		ret%=mod;
	}
	cout<<ret<<"\n";
}

void tof(){
	//cout<<porsted(1,1)<<" "<<porsjam(1,1)<<"\n";
	fres[stf[1].first]=hes(porsted(1,1)-1,val[1]-porsjam(1,1));
//	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);
	link[1]=0;
}
 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n>>k;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
//	segjam.upd(stf[1].first+kaf,k);
	val[1]=k;
	tof();
	long long q;
	cin>>q;
	asd=1;
//	cout<<res.seg[1]<<"\n";
	calres();
	for(;asd<=q;asd++){
		long long qq;
		cin>>qq;
		if(qq==1){
			long long u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			long long u;
			cin>>u;
			del(u);
		}
//		cout<<res.seg[1]<<"\n";
		calres();
	}
}

Compilation message

Main.cpp: In function 'void del(long long int)':
Main.cpp:236:12: warning: unused variable 'jam' [-Wunused-variable]
  236 |  long long jam=porsjam(u,u);
      |            ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 288740 KB Output is correct
2 Correct 297 ms 288548 KB Output is correct
3 Correct 306 ms 288620 KB Output is correct
4 Correct 299 ms 288648 KB Output is correct
5 Correct 283 ms 285808 KB Output is correct
6 Correct 190 ms 261856 KB Output is correct
7 Correct 196 ms 261644 KB Output is correct
8 Correct 201 ms 261628 KB Output is correct
9 Correct 308 ms 280664 KB Output is correct
10 Correct 297 ms 280548 KB Output is correct
11 Correct 305 ms 280644 KB Output is correct
12 Correct 294 ms 279680 KB Output is correct
13 Correct 299 ms 286812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 261316 KB Output is correct
2 Correct 190 ms 261324 KB Output is correct
3 Correct 189 ms 261304 KB Output is correct
4 Correct 189 ms 261384 KB Output is correct
5 Correct 191 ms 261456 KB Output is correct
6 Correct 198 ms 261664 KB Output is correct
7 Correct 213 ms 261580 KB Output is correct
8 Correct 196 ms 261588 KB Output is correct
9 Correct 205 ms 261756 KB Output is correct
10 Correct 202 ms 261900 KB Output is correct
11 Correct 201 ms 261844 KB Output is correct
12 Correct 195 ms 261768 KB Output is correct
13 Correct 222 ms 261804 KB Output is correct
14 Correct 202 ms 261772 KB Output is correct
15 Correct 207 ms 262032 KB Output is correct
16 Correct 211 ms 261820 KB Output is correct
17 Correct 205 ms 261804 KB Output is correct
18 Correct 203 ms 261580 KB Output is correct
19 Correct 206 ms 261716 KB Output is correct
20 Correct 205 ms 261664 KB Output is correct
21 Correct 196 ms 261572 KB Output is correct
22 Correct 190 ms 261356 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 292548 KB Output is correct
2 Execution timed out 3048 ms 293052 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 284528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 288740 KB Output is correct
2 Correct 297 ms 288548 KB Output is correct
3 Correct 306 ms 288620 KB Output is correct
4 Correct 299 ms 288648 KB Output is correct
5 Correct 283 ms 285808 KB Output is correct
6 Correct 190 ms 261856 KB Output is correct
7 Correct 196 ms 261644 KB Output is correct
8 Correct 201 ms 261628 KB Output is correct
9 Correct 308 ms 280664 KB Output is correct
10 Correct 297 ms 280548 KB Output is correct
11 Correct 305 ms 280644 KB Output is correct
12 Correct 294 ms 279680 KB Output is correct
13 Correct 299 ms 286812 KB Output is correct
14 Correct 190 ms 261316 KB Output is correct
15 Correct 190 ms 261324 KB Output is correct
16 Correct 189 ms 261304 KB Output is correct
17 Correct 189 ms 261384 KB Output is correct
18 Correct 191 ms 261456 KB Output is correct
19 Correct 198 ms 261664 KB Output is correct
20 Correct 213 ms 261580 KB Output is correct
21 Correct 196 ms 261588 KB Output is correct
22 Correct 205 ms 261756 KB Output is correct
23 Correct 202 ms 261900 KB Output is correct
24 Correct 201 ms 261844 KB Output is correct
25 Correct 195 ms 261768 KB Output is correct
26 Correct 222 ms 261804 KB Output is correct
27 Correct 202 ms 261772 KB Output is correct
28 Correct 207 ms 262032 KB Output is correct
29 Correct 211 ms 261820 KB Output is correct
30 Correct 205 ms 261804 KB Output is correct
31 Correct 203 ms 261580 KB Output is correct
32 Correct 206 ms 261716 KB Output is correct
33 Correct 205 ms 261664 KB Output is correct
34 Correct 196 ms 261572 KB Output is correct
35 Correct 190 ms 261356 KB Output is correct
36 Correct 1609 ms 292548 KB Output is correct
37 Execution timed out 3048 ms 293052 KB Time limit exceeded
38 Halted 0 ms 0 KB -