oj.uz

Submission #935505

# Submission time Handle Problem Language Result Execution time Memory
935505 2024-02-29T08:23:25 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 47004 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=5e5+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]){
		ans*=comb(sz[z]-1,sz[z]+(mark[z]-mize[z])-1);
		ans%=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 165 ms 46992 KB Output is correct
2 Correct 137 ms 46996 KB Output is correct
3 Correct 139 ms 47004 KB Output is correct
4 Correct 177 ms 46844 KB Output is correct
5 Correct 124 ms 42836 KB Output is correct
6 Correct 61 ms 25684 KB Output is correct
7 Correct 62 ms 25428 KB Output is correct
8 Correct 61 ms 25428 KB Output is correct
9 Correct 142 ms 39404 KB Output is correct
10 Correct 148 ms 39348 KB Output is correct
11 Correct 131 ms 39160 KB Output is correct
12 Correct 123 ms 38804 KB Output is correct
13 Correct 149 ms 46164 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 25384 KB Output is correct
2 Incorrect 60 ms 25240 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 3039 ms 46804 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 3046 ms 40008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 46992 KB Output is correct
2 Correct 137 ms 46996 KB Output is correct
3 Correct 139 ms 47004 KB Output is correct
4 Correct 177 ms 46844 KB Output is correct
5 Correct 124 ms 42836 KB Output is correct
6 Correct 61 ms 25684 KB Output is correct
7 Correct 62 ms 25428 KB Output is correct
8 Correct 61 ms 25428 KB Output is correct
9 Correct 142 ms 39404 KB Output is correct
10 Correct 148 ms 39348 KB Output is correct
11 Correct 131 ms 39160 KB Output is correct
12 Correct 123 ms 38804 KB Output is correct
13 Correct 149 ms 46164 KB Output is correct
14 Correct 61 ms 25384 KB Output is correct
15 Incorrect 60 ms 25240 KB Output isn't correct
16 Halted 0 ms 0 KB -