oj.uz

Submission #947918

# Submission time Handle Problem Language Result Execution time Memory
947918 2024-03-17T09:11:03 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 406 ms 277232 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);

 			v2=seg[1].get(st[z],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],g[x]-v1);
			seg[1].up(st[z],(v1-g[x])*2);
 
			v1=seg[1].get(st[x],fn[x]+1);
			v2=seg[1].get(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{
			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=seg[1].get(st[x],fn[x]+1);
			v2=seg[1].get(st[z],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*2);
			
			v2=seg[1].get(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: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 174 ms 134452 KB Output is correct
2 Correct 153 ms 132436 KB Output is correct
3 Correct 146 ms 131156 KB Output is correct
4 Correct 169 ms 133968 KB Output is correct
5 Correct 176 ms 130672 KB Output is correct
6 Correct 85 ms 117072 KB Output is correct
7 Correct 83 ms 116900 KB Output is correct
8 Correct 65 ms 114748 KB Output is correct
9 Correct 170 ms 128596 KB Output is correct
10 Correct 168 ms 128848 KB Output is correct
11 Correct 191 ms 128872 KB Output is correct
12 Correct 136 ms 124736 KB Output is correct
13 Correct 156 ms 133296 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 112212 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 277 ms 277232 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 406 ms 269608 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 174 ms 134452 KB Output is correct
2 Correct 153 ms 132436 KB Output is correct
3 Correct 146 ms 131156 KB Output is correct
4 Correct 169 ms 133968 KB Output is correct
5 Correct 176 ms 130672 KB Output is correct
6 Correct 85 ms 117072 KB Output is correct
7 Correct 83 ms 116900 KB Output is correct
8 Correct 65 ms 114748 KB Output is correct
9 Correct 170 ms 128596 KB Output is correct
10 Correct 168 ms 128848 KB Output is correct
11 Correct 191 ms 128872 KB Output is correct
12 Correct 136 ms 124736 KB Output is correct
13 Correct 156 ms 133296 KB Output is correct
14 Incorrect 47 ms 112212 KB Output isn't correct
15 Halted 0 ms 0 KB -