oj.uz

Submission #947885

# Submission time Handle Problem Language Result Execution time Memory
947885 2024-03-17T08:03:56 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 282708 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]-t1;
			int sz2=sz[z]-t2-sz1;

			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);
			
			sz2=t2+sz[x]-t1;

			seg[1].up(1,1,n+1,st[x],-v1);
			seg[1].up(1,1,n+1,st[z],v1);
			
			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 176 ms 135248 KB Output is correct
2 Correct 165 ms 132820 KB Output is correct
3 Correct 178 ms 131668 KB Output is correct
4 Correct 163 ms 134224 KB Output is correct
5 Correct 157 ms 131040 KB Output is correct
6 Correct 87 ms 117588 KB Output is correct
7 Correct 87 ms 117328 KB Output is correct
8 Correct 70 ms 115280 KB Output is correct
9 Correct 176 ms 129004 KB Output is correct
10 Correct 169 ms 129068 KB Output is correct
11 Correct 182 ms 129104 KB Output is correct
12 Correct 189 ms 125316 KB Output is correct
13 Correct 160 ms 133684 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 282 ms 282708 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 578 ms 281168 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 176 ms 135248 KB Output is correct
2 Correct 165 ms 132820 KB Output is correct
3 Correct 178 ms 131668 KB Output is correct
4 Correct 163 ms 134224 KB Output is correct
5 Correct 157 ms 131040 KB Output is correct
6 Correct 87 ms 117588 KB Output is correct
7 Correct 87 ms 117328 KB Output is correct
8 Correct 70 ms 115280 KB Output is correct
9 Correct 176 ms 129004 KB Output is correct
10 Correct 169 ms 129068 KB Output is correct
11 Correct 182 ms 129104 KB Output is correct
12 Correct 189 ms 125316 KB Output is correct
13 Correct 160 ms 133684 KB Output is correct
14 Execution timed out 3063 ms 112420 KB Time limit exceeded
15 Halted 0 ms 0 KB -