oj.uz

Submission #935557

# Submission time Handle Problem Language Result Execution time Memory
935557 2024-02-29T09:08:35 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 49380 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=6e5+5,M=1e9+7;
int n,q,r;
ll fuck[mxn],rfuck[mxn],ans=1,par[mxn],mark[mxn],sz[mxn],mize[mxn];
vector<int>v[mxn];
ll ferma(ll x){
	ll res=1,num=M-2;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num/=2;
	}
	return res;
}
ll comb(ll x,ll y){
	return (((fuck[y]*rfuck[x])%M)*rfuck[y-x])%M;
}
void dfs(int z){
	sz[z]=1;
	mize[z]=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dfs(i);
			sz[z]+=sz[i];
			mize[z]+=mize[i];
		}
	}
	if(mark[z]){
		assert(mark[z]>=mize[z]);
		ans=(ans*comb(sz[z]-1,sz[z]+(mark[z]-mize[z])-1))%M;
		mize[z]=mark[z];
		sz[z]=0;//cout<<z<<" "<<comb(sz[z]-1,sz[z]+(mark[z]-mize[z])-1)<<'\n';
	}
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	fuck[0]=1;
	rfuck[0]=1;
	for(int i=1;i<mxn;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	mark[1]=r;
	dfs(1);
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		ans=1;
		int ty,x,y;
		cin>>ty;
		if(ty==1){
			cin>>x>>y;
			mark[x]=y;
		}
		else{
			cin>>x;
			mark[x]=0;
		}
		dfs(1);
		cout<<ans%M<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 49172 KB Output is correct
2 Correct 171 ms 49304 KB Output is correct
3 Correct 192 ms 49380 KB Output is correct
4 Correct 189 ms 49308 KB Output is correct
5 Correct 175 ms 45400 KB Output is correct
6 Correct 73 ms 30548 KB Output is correct
7 Correct 74 ms 30484 KB Output is correct
8 Correct 75 ms 30360 KB Output is correct
9 Correct 187 ms 41632 KB Output is correct
10 Correct 143 ms 41652 KB Output is correct
11 Correct 149 ms 41680 KB Output is correct
12 Correct 167 ms 41320 KB Output is correct
13 Correct 140 ms 48536 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 30356 KB Output is correct
2 Incorrect 73 ms 30288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 48872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 42036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 49172 KB Output is correct
2 Correct 171 ms 49304 KB Output is correct
3 Correct 192 ms 49380 KB Output is correct
4 Correct 189 ms 49308 KB Output is correct
5 Correct 175 ms 45400 KB Output is correct
6 Correct 73 ms 30548 KB Output is correct
7 Correct 74 ms 30484 KB Output is correct
8 Correct 75 ms 30360 KB Output is correct
9 Correct 187 ms 41632 KB Output is correct
10 Correct 143 ms 41652 KB Output is correct
11 Correct 149 ms 41680 KB Output is correct
12 Correct 167 ms 41320 KB Output is correct
13 Correct 140 ms 48536 KB Output is correct
14 Correct 72 ms 30356 KB Output is correct
15 Incorrect 73 ms 30288 KB Output isn't correct
16 Halted 0 ms 0 KB -