oj.uz

Submission #1036738

# Submission time Handle Problem Language Result Execution time Memory
1036738 2024-07-27T16:15:00 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 492 ms 282964 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);
ll n,q,r,st[mxn],fn[mxn],cnt=0,sz[mxn],g[mxn],bbb;
ll ans,fuck[mxn*2],rfuck[mxn*2];
vector<ll>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>>=1;
	}
	return res;
}
void dfs(ll 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(ll i=1;i<=n+r;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
}
ll comb(ll x,ll 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(ll id,ll L,ll R,ll l,ll x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		ll 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(ll id ,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return val[id];
		ll 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<ll>s[kkk];
	ll get(ll id,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return ((s[id].size())?*s[id].rbegin():0);
		ll 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(ll id ,ll L,ll R,ll l,ll r,ll x,bool y){
		if(L==l && R==r){
			if(y)
				s[id].insert(x);
			else
				s[id].erase(x);
			return;
		}
		ll 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(ll i=1;i<n;i++){
		ll 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--){
		ll 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 t1=seg[0].get(1,1,n+1,st[x],fn[x]+1)-seg[0].get(1,1,n+1,st[x],st[x]+1);
		ll t2=seg[0].get(1,1,n+1,st[z],fn[z]+1)-seg[0].get(1,1,n+1,st[z],st[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){
			ll sz1=sz[x]-t1;
			ll sz2=sz[z]-t2-sz1;
			seg[0].up(1,1,n+1,st[x],sz1);
			seg[0].up(1,1,n+1,st[z],sz2);

			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;
			//cout<<comb(sz[z]-t2-1,sz[z]-t2+v2-1,1)<<" ";
			ll val1=comb(sz1-1,sz1-1+g[x]-v1,0);
			ll val2=comb(sz2-1,sz2-1+v2-g[x]+v1,0);
			ans*=val1;
			ans%=M;
			ans*=val2;
			ans%=M;
			seg[1].up(1,1,n+1,st[x],g[x]-v1-v1);
			seg[1].up(1,1,n+1,st[z],0);
			ll w=seg[1].get(1,1,n+1,st[z],fn[z]+1);
			seg[1].up(1,1,n+1,st[z],g[z]-w-w);
		}
		else{
			ll sz1=sz[x]-t1;
			ll sz2=sz[z]-t2+sz1;
			seg[0].up(1,1,n+1,st[x],0);
			seg[0].up(1,1,n+1,st[z],sz2);
			//cout<<v1<<" "<<v2<<'\n';
			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;

			ll val1=comb(sz2-1,sz2-1+v2+v1,0);
			ans*=val1;
			ans%=M;

			seg[1].up(1,1,n+1,st[x],0);
			seg[1].up(1,1,n+1,st[z],0);
			ll w=seg[1].get(1,1,n+1,st[z],fn[z]+1);
			seg[1].up(1,1,n+1,st[z],g[z]-w-w);

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 138836 KB Output is correct
2 Correct 160 ms 136788 KB Output is correct
3 Correct 142 ms 135508 KB Output is correct
4 Correct 175 ms 138324 KB Output is correct
5 Correct 161 ms 134228 KB Output is correct
6 Correct 83 ms 115780 KB Output is correct
7 Correct 85 ms 115712 KB Output is correct
8 Correct 65 ms 113236 KB Output is correct
9 Correct 175 ms 132844 KB Output is correct
10 Correct 170 ms 132948 KB Output is correct
11 Correct 175 ms 133056 KB Output is correct
12 Correct 140 ms 128852 KB Output is correct
13 Correct 161 ms 136840 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 110680 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 276 ms 282964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 138836 KB Output is correct
2 Correct 160 ms 136788 KB Output is correct
3 Correct 142 ms 135508 KB Output is correct
4 Correct 175 ms 138324 KB Output is correct
5 Correct 161 ms 134228 KB Output is correct
6 Correct 83 ms 115780 KB Output is correct
7 Correct 85 ms 115712 KB Output is correct
8 Correct 65 ms 113236 KB Output is correct
9 Correct 175 ms 132844 KB Output is correct
10 Correct 170 ms 132948 KB Output is correct
11 Correct 175 ms 133056 KB Output is correct
12 Correct 140 ms 128852 KB Output is correct
13 Correct 161 ms 136840 KB Output is correct
14 Incorrect 45 ms 110680 KB Output isn't correct
15 Halted 0 ms 0 KB -