oj.uz

Submission #947688

# Submission time Handle Problem Language Result Execution time Memory
947688 2024-03-16T20:17:14 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 261 ms 278380 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){
		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(int id,int L,int R,int l,int x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		int 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(int id ,int L,int R,int l,int r){
		if(L==l && R==r)
			return val[id];
		int 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<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,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--){
		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);
		}
		
		
		int t1=seg[0].get(1,1,n+1,st[x],fn[x]+1);
		int t2=seg[0].get(1,1,n+1,st[z],fn[z]+1);
		ll v1=0;
		ll v2=0;
		if(ty==1){
			int sz1=sz[x]-t1;
			int 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)<<" ";
			int val1=comb(sz1-1,sz1-1+g[x]-v1,0);
			int val2=comb(sz2-1,sz2-1+v2-g[x]+v1,0);
			ans*=val1;
			ans%=M;
			ans*=val2;
			ans%=M;
			
		}
		
		if(bbb){
			cout<<0<<'\n';
		}
		else
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:12: warning: unused variable 'y' [-Wunused-variable]
  120 |   int ty,x,y,z;
      |            ^
Main.cpp:139:35: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |    ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
      |                               ~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 134756 KB Output is correct
2 Correct 131 ms 132964 KB Output is correct
3 Correct 123 ms 131672 KB Output is correct
4 Correct 138 ms 134224 KB Output is correct
5 Correct 132 ms 131052 KB Output is correct
6 Correct 60 ms 117588 KB Output is correct
7 Correct 60 ms 117412 KB Output is correct
8 Correct 44 ms 115292 KB Output is correct
9 Correct 142 ms 128824 KB Output is correct
10 Correct 141 ms 129128 KB Output is correct
11 Correct 160 ms 129296 KB Output is correct
12 Correct 113 ms 125464 KB Output is correct
13 Correct 148 ms 133460 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 113244 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 257 ms 278380 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 261 ms 139088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 134756 KB Output is correct
2 Correct 131 ms 132964 KB Output is correct
3 Correct 123 ms 131672 KB Output is correct
4 Correct 138 ms 134224 KB Output is correct
5 Correct 132 ms 131052 KB Output is correct
6 Correct 60 ms 117588 KB Output is correct
7 Correct 60 ms 117412 KB Output is correct
8 Correct 44 ms 115292 KB Output is correct
9 Correct 142 ms 128824 KB Output is correct
10 Correct 141 ms 129128 KB Output is correct
11 Correct 160 ms 129296 KB Output is correct
12 Correct 113 ms 125464 KB Output is correct
13 Correct 148 ms 133460 KB Output is correct
14 Incorrect 25 ms 113244 KB Output isn't correct
15 Halted 0 ms 0 KB -