oj.uz

Submission #947923

# Submission time Handle Problem Language Result Execution time Memory
947923 2024-03-17T09:19:16 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 299 ms 277336 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 || x<0 || y<0){
		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[mxn];
	void up(int id,ll x){
		for(;id<n;id+=id&(-id))
			val[id]+=x;
	}
	ll get(int id){
		ll res=0;
		for(;id>0;id-=id&(-id))
			res+=val[id];
		return res;
	}
	ll get(int L,int R){
		return get(R-1)-get(L-1);
	}
}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,n);
	seg[1].up(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);
		}
		ll v2,v1,t1,t2;
		if(ty==1){
			t1=seg[0].get(st[x]+1,fn[x]+1);
			t2=seg[0].get(st[z]+1,fn[z]+1);

			seg[0].up(st[x],sz[x]-t1);
			seg[0].up(st[z],-sz[x]+t1);

			v1=g[x]-seg[1].get(st[x]+1,fn[x]+1);
			v2=g[z]-seg[1].get(st[z]+1,fn[z]+1);
 			
			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;

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

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

			int sz1=sz[x]-t1;
			int sz2=sz[z]-t2;
 			
 			v1=g[x]-seg[1].get(st[x]+1,fn[x]+1);
			v2=g[z]-seg[1].get(st[z]+1,fn[z]+1);

			ans*=ferma(comb(sz1-1,sz1+v1-1,1));
			ans%=M;
			ans*=ferma(comb(sz2-1,sz2+v2-1,1));
			ans%=M;
 
			seg[0].up(st[x],-sz1);
			seg[0].up(st[z],sz1);
			
			sz2+=sz1;
 
			seg[1].up(st[x],-v1);
			seg[1].up(st[z],v1);
			
			int val1=comb(sz2-1,sz2-1+v2+v1,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:111:12: warning: unused variable 'y' [-Wunused-variable]
  111 |   int ty,x,y,z;
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 134268 KB Output is correct
2 Correct 153 ms 132444 KB Output is correct
3 Correct 148 ms 131384 KB Output is correct
4 Correct 165 ms 133972 KB Output is correct
5 Correct 169 ms 130680 KB Output is correct
6 Correct 83 ms 117120 KB Output is correct
7 Correct 83 ms 117072 KB Output is correct
8 Correct 68 ms 114880 KB Output is correct
9 Correct 165 ms 128596 KB Output is correct
10 Correct 172 ms 128852 KB Output is correct
11 Correct 184 ms 128852 KB Output is correct
12 Correct 144 ms 124872 KB Output is correct
13 Correct 157 ms 133144 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 112208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 299 ms 277336 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 271 ms 268236 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 184 ms 134268 KB Output is correct
2 Correct 153 ms 132444 KB Output is correct
3 Correct 148 ms 131384 KB Output is correct
4 Correct 165 ms 133972 KB Output is correct
5 Correct 169 ms 130680 KB Output is correct
6 Correct 83 ms 117120 KB Output is correct
7 Correct 83 ms 117072 KB Output is correct
8 Correct 68 ms 114880 KB Output is correct
9 Correct 165 ms 128596 KB Output is correct
10 Correct 172 ms 128852 KB Output is correct
11 Correct 184 ms 128852 KB Output is correct
12 Correct 144 ms 124872 KB Output is correct
13 Correct 157 ms 133144 KB Output is correct
14 Incorrect 49 ms 112208 KB Output isn't correct
15 Halted 0 ms 0 KB -