oj.uz

Submission #784038

# Submission time Handle Problem Language Result Execution time Memory
784038 2023-07-15T15:13:13 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 292284 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);
//	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);
//	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:235:12: warning: unused variable 'jam' [-Wunused-variable]
  235 |  long long jam=porsjam(u,u);
      |            ^~~
Main.cpp:237:12: warning: unused variable 'ted' [-Wunused-variable]
  237 |  long long ted=porsted(u,u);
      |            ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 288308 KB Output is correct
2 Correct 292 ms 288280 KB Output is correct
3 Correct 295 ms 288332 KB Output is correct
4 Correct 293 ms 288300 KB Output is correct
5 Correct 287 ms 285656 KB Output is correct
6 Correct 190 ms 261856 KB Output is correct
7 Correct 189 ms 261580 KB Output is correct
8 Correct 200 ms 261720 KB Output is correct
9 Correct 316 ms 280416 KB Output is correct
10 Correct 315 ms 280204 KB Output is correct
11 Correct 310 ms 280360 KB Output is correct
12 Correct 294 ms 279352 KB Output is correct
13 Correct 289 ms 286440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 261312 KB Output is correct
2 Correct 189 ms 261324 KB Output is correct
3 Correct 190 ms 261448 KB Output is correct
4 Correct 188 ms 261296 KB Output is correct
5 Correct 190 ms 261344 KB Output is correct
6 Correct 196 ms 261568 KB Output is correct
7 Correct 198 ms 261608 KB Output is correct
8 Correct 197 ms 261596 KB Output is correct
9 Correct 216 ms 261712 KB Output is correct
10 Correct 202 ms 261720 KB Output is correct
11 Correct 200 ms 261760 KB Output is correct
12 Correct 190 ms 261728 KB Output is correct
13 Correct 201 ms 261832 KB Output is correct
14 Correct 201 ms 261764 KB Output is correct
15 Correct 201 ms 261936 KB Output is correct
16 Correct 218 ms 261772 KB Output is correct
17 Correct 207 ms 261748 KB Output is correct
18 Correct 195 ms 261576 KB Output is correct
19 Correct 217 ms 261652 KB Output is correct
20 Correct 196 ms 261588 KB Output is correct
21 Correct 197 ms 261580 KB Output is correct
22 Correct 188 ms 261356 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 289224 KB Output is correct
2 Execution timed out 3086 ms 292284 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 3063 ms 281512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 288308 KB Output is correct
2 Correct 292 ms 288280 KB Output is correct
3 Correct 295 ms 288332 KB Output is correct
4 Correct 293 ms 288300 KB Output is correct
5 Correct 287 ms 285656 KB Output is correct
6 Correct 190 ms 261856 KB Output is correct
7 Correct 189 ms 261580 KB Output is correct
8 Correct 200 ms 261720 KB Output is correct
9 Correct 316 ms 280416 KB Output is correct
10 Correct 315 ms 280204 KB Output is correct
11 Correct 310 ms 280360 KB Output is correct
12 Correct 294 ms 279352 KB Output is correct
13 Correct 289 ms 286440 KB Output is correct
14 Correct 186 ms 261312 KB Output is correct
15 Correct 189 ms 261324 KB Output is correct
16 Correct 190 ms 261448 KB Output is correct
17 Correct 188 ms 261296 KB Output is correct
18 Correct 190 ms 261344 KB Output is correct
19 Correct 196 ms 261568 KB Output is correct
20 Correct 198 ms 261608 KB Output is correct
21 Correct 197 ms 261596 KB Output is correct
22 Correct 216 ms 261712 KB Output is correct
23 Correct 202 ms 261720 KB Output is correct
24 Correct 200 ms 261760 KB Output is correct
25 Correct 190 ms 261728 KB Output is correct
26 Correct 201 ms 261832 KB Output is correct
27 Correct 201 ms 261764 KB Output is correct
28 Correct 201 ms 261936 KB Output is correct
29 Correct 218 ms 261772 KB Output is correct
30 Correct 207 ms 261748 KB Output is correct
31 Correct 195 ms 261576 KB Output is correct
32 Correct 217 ms 261652 KB Output is correct
33 Correct 196 ms 261588 KB Output is correct
34 Correct 197 ms 261580 KB Output is correct
35 Correct 188 ms 261356 KB Output is correct
36 Correct 1672 ms 289224 KB Output is correct
37 Execution timed out 3086 ms 292284 KB Time limit exceeded
38 Halted 0 ms 0 KB -