oj.uz

Submission #947880

# Submission time Handle Problem Language Result Execution time Memory
947880 2024-03-17T07:59:40 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 285312 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
const int mxn=5e5+5,M=1e9+7,kkk=(1<<21);
int n,q,r,st[mxn],fn[mxn],cnt=0,sz[mxn],g[mxn],bbb;
ll ans,fuck[mxn],rfuck[mxn];
vector<int>v[mxn];
ll ferma(ll x){
	ll num=M-2,res=1;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num/=2;
	}
	return res;
}
void dfs(int z){
	sz[z]=1;
	st[z]=++cnt;
	for(auto i:v[z]){
		if(!st[i]){
			dfs(i);
			sz[z]+=sz[i];
		}
	}
	fn[z]=cnt;
}
void make(){
	fuck[0]=rfuck[0]=1;
	for(int i=1;i<=n+r;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
}
ll comb(int x,int y,bool w){
	if(x>y){
		bbb+=(w)?-1:1;
		return 1;
	}
	ll res=fuck[y]*rfuck[x];
	res%=M;
	res*=rfuck[y-x];
	return res%M;
}
struct segment{
	ll val[kkk];
	void up(int id,int L,int R,int l,ll x){
		if(L+1==R){
			val[id]+=x;
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x);
		else
			up(id*2+1,mid,R,l,x);
		val[id]=val[id*2]+val[id*2+1];
	}
	ll get(int id ,int L,int R,int l,int r){
		if(L==l && R==r)
			return val[id];
		int mid=(L+R)/2;
		ll res=0;
		if(l<mid)
			res+=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			res+=get(id*2+1,mid,R,max(l,mid),r);
		return res;
	}
}seg[2];
struct fnd{
	set<int>s[kkk];
	int get(int id,int L,int R,int l,int r){
		if(L==l && R==r)
			return ((s[id].size())?*s[id].rbegin():0);
		int mid=(L+R)/2,res=((s[id].size())?*s[id].rbegin():0),x=0;
		if(l<mid){
			x=get(id*2,L,mid,l,min(r,mid));
		}
		return (x)?x:res;
	}
	void add(int id ,int L,int R,int l,int r,int x,bool y){
		if(L==l && R==r){
			if(y)
				s[id].insert(x);
			else
				s[id].erase(x);
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			add(id*2,L,mid,l,min(r,mid),x,y);
		if(r>mid)
			add(id*2+1,mid,R,max(l,mid),r,x,y);
	}
}fnd;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	make();
	ans=comb(n-1,n+r-1,0);
	seg[0].up(1,1,n+1,1,n);
	seg[1].up(1,1,n+1,1,r);
	fnd.add(1,1,n+1,1,n+1,1,1);
	g[1]=r;
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		int ty,x,y,z;
		cin>>ty;
		if(ty==1){
			cin>>x>>g[x];
			z=fnd.get(1,1,n+1,st[x],fn[x]+1);
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],1);
		}
		else{
			cin>>x;
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],0);
			 z=fnd.get(1,1,n+1,st[x],fn[x]+1);
		}

		int t1=seg[0].get(1,1,n+1,st[x]+1,fn[x]+1);
		int t2=seg[0].get(1,1,n+1,st[z]+1,fn[z]+1);
		ll v1=seg[1].get(1,1,n+1,st[x],fn[x]+1);
		ll v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);
		if(ty==1){
			seg[0].up(1,1,n+1,st[x],sz[x]-t1);
			seg[0].up(1,1,n+1,st[z],-sz[x]+t1);

			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;
			
			int sz1=sz[x]-seg[0].get(1,1,n+1,st[x]+1,fn[x]+1);
			int sz2=sz[z]-seg[0].get(1,1,n+1,st[z]+1,fn[z]+1);

			seg[1].up(1,1,n+1,st[x],g[x]-v1);
			seg[1].up(1,1,n+1,st[z],v1-g[x]);

			v1=seg[1].get(1,1,n+1,st[x],fn[x]+1);
			v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);

			int val1=comb(sz1-1,sz1-1+v1,0);
			int val2=comb(sz2-1,sz2-1+v2,0);
			ans*=val1;
			ans%=M;
			ans*=val2;
			ans%=M;
			
		}
		else{
			
			int sz1=sz[x]-seg[0].get(1,1,n+1,st[x]+1,fn[x]+1);
			int sz2=sz[z]-seg[0].get(1,1,n+1,st[z]+1,fn[z]+1);

			ans*=ferma(comb(sz1-1,sz1+v1-1,1));
			ans%=M;
			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;

			seg[0].up(1,1,n+1,st[x],-sz[x]+t1);
			seg[0].up(1,1,n+1,st[z],sz[x]-t1);
			
			sz1=sz[x]-seg[0].get(1,1,n+1,st[x]+1,fn[x]+1);
			sz2=sz[z]-seg[0].get(1,1,n+1,st[z]+1,fn[z]+1);

			seg[1].up(1,1,n+1,st[x],-t1);
			seg[1].up(1,1,n+1,st[z],t1);
			
			v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);
			int val1=comb(sz2-1,sz2-1+v2,0);
			ans*=val1;
			ans%=M;

		}
		if(bbb){
			cout<<0<<'\n';
		}
		else
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:12: warning: unused variable 'y' [-Wunused-variable]
  120 |   int ty,x,y,z;
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 137296 KB Output is correct
2 Correct 166 ms 135248 KB Output is correct
3 Correct 162 ms 134028 KB Output is correct
4 Correct 183 ms 136816 KB Output is correct
5 Correct 201 ms 131636 KB Output is correct
6 Correct 84 ms 117544 KB Output is correct
7 Correct 84 ms 116016 KB Output is correct
8 Correct 75 ms 113260 KB Output is correct
9 Correct 199 ms 129552 KB Output is correct
10 Correct 200 ms 131668 KB Output is correct
11 Correct 233 ms 131888 KB Output is correct
12 Correct 167 ms 125540 KB Output is correct
13 Correct 162 ms 135764 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 285312 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 326 ms 282296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 137296 KB Output is correct
2 Correct 166 ms 135248 KB Output is correct
3 Correct 162 ms 134028 KB Output is correct
4 Correct 183 ms 136816 KB Output is correct
5 Correct 201 ms 131636 KB Output is correct
6 Correct 84 ms 117544 KB Output is correct
7 Correct 84 ms 116016 KB Output is correct
8 Correct 75 ms 113260 KB Output is correct
9 Correct 199 ms 129552 KB Output is correct
10 Correct 200 ms 131668 KB Output is correct
11 Correct 233 ms 131888 KB Output is correct
12 Correct 167 ms 125540 KB Output is correct
13 Correct 162 ms 135764 KB Output is correct
14 Execution timed out 3080 ms 112580 KB Time limit exceeded
15 Halted 0 ms 0 KB -