oj.uz

Submission #947926

# Submission time Handle Problem Language Result Execution time Memory
947926 2024-03-17T09:23:53 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 389 ms 277312 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;

			

			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 168 ms 134480 KB Output is correct
2 Correct 155 ms 132308 KB Output is correct
3 Correct 157 ms 131148 KB Output is correct
4 Correct 163 ms 134012 KB Output is correct
5 Correct 171 ms 130644 KB Output is correct
6 Correct 86 ms 117216 KB Output is correct
7 Correct 83 ms 116940 KB Output is correct
8 Correct 65 ms 114668 KB Output is correct
9 Correct 167 ms 128420 KB Output is correct
10 Correct 195 ms 128760 KB Output is correct
11 Correct 170 ms 128824 KB Output is correct
12 Correct 135 ms 124728 KB Output is correct
13 Correct 175 ms 133292 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 112216 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 273 ms 277312 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 389 ms 268520 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 168 ms 134480 KB Output is correct
2 Correct 155 ms 132308 KB Output is correct
3 Correct 157 ms 131148 KB Output is correct
4 Correct 163 ms 134012 KB Output is correct
5 Correct 171 ms 130644 KB Output is correct
6 Correct 86 ms 117216 KB Output is correct
7 Correct 83 ms 116940 KB Output is correct
8 Correct 65 ms 114668 KB Output is correct
9 Correct 167 ms 128420 KB Output is correct
10 Correct 195 ms 128760 KB Output is correct
11 Correct 170 ms 128824 KB Output is correct
12 Correct 135 ms 124728 KB Output is correct
13 Correct 175 ms 133292 KB Output is correct
14 Incorrect 52 ms 112216 KB Output isn't correct
15 Halted 0 ms 0 KB -