oj.uz

Submission #784047

# Submission time Handle Problem Language Result Execution time Memory
784047 2023-07-15T15:28:36 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 299140 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 307 ms 288284 KB Output is correct
2 Correct 312 ms 288384 KB Output is correct
3 Correct 296 ms 288272 KB Output is correct
4 Correct 292 ms 288284 KB Output is correct
5 Correct 316 ms 285524 KB Output is correct
6 Correct 191 ms 261756 KB Output is correct
7 Correct 190 ms 261592 KB Output is correct
8 Correct 222 ms 261592 KB Output is correct
9 Correct 304 ms 280308 KB Output is correct
10 Correct 309 ms 280372 KB Output is correct
11 Correct 320 ms 280388 KB Output is correct
12 Correct 297 ms 279428 KB Output is correct
13 Correct 295 ms 286596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 261316 KB Output is correct
2 Correct 187 ms 261312 KB Output is correct
3 Correct 193 ms 261284 KB Output is correct
4 Correct 190 ms 261380 KB Output is correct
5 Correct 190 ms 261424 KB Output is correct
6 Correct 209 ms 261708 KB Output is correct
7 Correct 197 ms 261644 KB Output is correct
8 Correct 206 ms 261624 KB Output is correct
9 Correct 207 ms 261732 KB Output is correct
10 Correct 203 ms 261916 KB Output is correct
11 Correct 204 ms 262060 KB Output is correct
12 Correct 194 ms 261780 KB Output is correct
13 Correct 204 ms 261964 KB Output is correct
14 Correct 203 ms 261972 KB Output is correct
15 Correct 206 ms 262388 KB Output is correct
16 Correct 217 ms 261816 KB Output is correct
17 Correct 205 ms 261948 KB Output is correct
18 Correct 207 ms 261868 KB Output is correct
19 Correct 217 ms 261692 KB Output is correct
20 Correct 211 ms 261664 KB Output is correct
21 Correct 198 ms 261676 KB Output is correct
22 Correct 199 ms 261412 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 295640 KB Output is correct
2 Execution timed out 3066 ms 299140 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 3032 ms 284912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 288284 KB Output is correct
2 Correct 312 ms 288384 KB Output is correct
3 Correct 296 ms 288272 KB Output is correct
4 Correct 292 ms 288284 KB Output is correct
5 Correct 316 ms 285524 KB Output is correct
6 Correct 191 ms 261756 KB Output is correct
7 Correct 190 ms 261592 KB Output is correct
8 Correct 222 ms 261592 KB Output is correct
9 Correct 304 ms 280308 KB Output is correct
10 Correct 309 ms 280372 KB Output is correct
11 Correct 320 ms 280388 KB Output is correct
12 Correct 297 ms 279428 KB Output is correct
13 Correct 295 ms 286596 KB Output is correct
14 Correct 198 ms 261316 KB Output is correct
15 Correct 187 ms 261312 KB Output is correct
16 Correct 193 ms 261284 KB Output is correct
17 Correct 190 ms 261380 KB Output is correct
18 Correct 190 ms 261424 KB Output is correct
19 Correct 209 ms 261708 KB Output is correct
20 Correct 197 ms 261644 KB Output is correct
21 Correct 206 ms 261624 KB Output is correct
22 Correct 207 ms 261732 KB Output is correct
23 Correct 203 ms 261916 KB Output is correct
24 Correct 204 ms 262060 KB Output is correct
25 Correct 194 ms 261780 KB Output is correct
26 Correct 204 ms 261964 KB Output is correct
27 Correct 203 ms 261972 KB Output is correct
28 Correct 206 ms 262388 KB Output is correct
29 Correct 217 ms 261816 KB Output is correct
30 Correct 205 ms 261948 KB Output is correct
31 Correct 207 ms 261868 KB Output is correct
32 Correct 217 ms 261692 KB Output is correct
33 Correct 211 ms 261664 KB Output is correct
34 Correct 198 ms 261676 KB Output is correct
35 Correct 199 ms 261412 KB Output is correct
36 Correct 1572 ms 295640 KB Output is correct
37 Execution timed out 3066 ms 299140 KB Time limit exceeded
38 Halted 0 ms 0 KB -