oj.uz

Submission #947933

# Submission time Handle Problem Language Result Execution time Memory
947933 2024-03-17T09:29:36 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 420 ms 275788 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);

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

			ans*=ferma(comb(sz2+sz1-1,sz2+sz1+v2-1,1));
			ans%=M;

			seg[0].up(st[x],sz1);
			seg[0].up(st[z],-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 176 ms 135952 KB Output is correct
2 Correct 167 ms 133972 KB Output is correct
3 Correct 145 ms 132848 KB Output is correct
4 Correct 166 ms 135420 KB Output is correct
5 Correct 159 ms 132336 KB Output is correct
6 Correct 82 ms 117076 KB Output is correct
7 Correct 86 ms 116940 KB Output is correct
8 Correct 66 ms 114720 KB Output is correct
9 Correct 174 ms 130172 KB Output is correct
10 Correct 211 ms 130364 KB Output is correct
11 Correct 187 ms 128792 KB Output is correct
12 Correct 161 ms 124660 KB Output is correct
13 Correct 166 ms 133048 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 110684 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 335 ms 275788 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 420 ms 271056 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 135952 KB Output is correct
2 Correct 167 ms 133972 KB Output is correct
3 Correct 145 ms 132848 KB Output is correct
4 Correct 166 ms 135420 KB Output is correct
5 Correct 159 ms 132336 KB Output is correct
6 Correct 82 ms 117076 KB Output is correct
7 Correct 86 ms 116940 KB Output is correct
8 Correct 66 ms 114720 KB Output is correct
9 Correct 174 ms 130172 KB Output is correct
10 Correct 211 ms 130364 KB Output is correct
11 Correct 187 ms 128792 KB Output is correct
12 Correct 161 ms 124660 KB Output is correct
13 Correct 166 ms 133048 KB Output is correct
14 Incorrect 48 ms 110684 KB Output isn't correct
15 Halted 0 ms 0 KB -