oj.uz

Submission #935549

# Submission time Handle Problem Language Result Execution time Memory
935549 2024-02-29T09:05:35 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 51144 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]){
		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);
		assert(ans>=0);
		cout<<ans%M<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 51124 KB Output is correct
2 Correct 166 ms 50912 KB Output is correct
3 Correct 191 ms 51144 KB Output is correct
4 Correct 180 ms 51024 KB Output is correct
5 Correct 154 ms 47216 KB Output is correct
6 Correct 74 ms 30628 KB Output is correct
7 Correct 73 ms 30548 KB Output is correct
8 Correct 74 ms 30548 KB Output is correct
9 Correct 140 ms 43348 KB Output is correct
10 Correct 200 ms 43428 KB Output is correct
11 Correct 156 ms 43464 KB Output is correct
12 Correct 147 ms 42932 KB Output is correct
13 Correct 165 ms 50256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 30356 KB Output is correct
2 Incorrect 72 ms 30356 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 3050 ms 50892 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 3090 ms 43808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 51124 KB Output is correct
2 Correct 166 ms 50912 KB Output is correct
3 Correct 191 ms 51144 KB Output is correct
4 Correct 180 ms 51024 KB Output is correct
5 Correct 154 ms 47216 KB Output is correct
6 Correct 74 ms 30628 KB Output is correct
7 Correct 73 ms 30548 KB Output is correct
8 Correct 74 ms 30548 KB Output is correct
9 Correct 140 ms 43348 KB Output is correct
10 Correct 200 ms 43428 KB Output is correct
11 Correct 156 ms 43464 KB Output is correct
12 Correct 147 ms 42932 KB Output is correct
13 Correct 165 ms 50256 KB Output is correct
14 Correct 78 ms 30356 KB Output is correct
15 Incorrect 72 ms 30356 KB Output isn't correct
16 Halted 0 ms 0 KB -