oj.uz

Submission #935514

# Submission time Handle Problem Language Result Execution time Memory
935514 2024-02-29T08:29:45 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=(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 134 ms 46928 KB Output is correct
2 Correct 146 ms 46792 KB Output is correct
3 Correct 142 ms 46992 KB Output is correct
4 Correct 134 ms 47004 KB Output is correct
5 Correct 129 ms 42896 KB Output is correct
6 Correct 61 ms 25756 KB Output is correct
7 Correct 61 ms 25496 KB Output is correct
8 Correct 62 ms 25424 KB Output is correct
9 Correct 145 ms 39252 KB Output is correct
10 Correct 159 ms 39236 KB Output is correct
11 Correct 148 ms 39464 KB Output is correct
12 Correct 130 ms 39000 KB Output is correct
13 Correct 124 ms 46164 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25168 KB Output is correct
2 Incorrect 62 ms 25228 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 3009 ms 46404 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 3049 ms 39824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 46928 KB Output is correct
2 Correct 146 ms 46792 KB Output is correct
3 Correct 142 ms 46992 KB Output is correct
4 Correct 134 ms 47004 KB Output is correct
5 Correct 129 ms 42896 KB Output is correct
6 Correct 61 ms 25756 KB Output is correct
7 Correct 61 ms 25496 KB Output is correct
8 Correct 62 ms 25424 KB Output is correct
9 Correct 145 ms 39252 KB Output is correct
10 Correct 159 ms 39236 KB Output is correct
11 Correct 148 ms 39464 KB Output is correct
12 Correct 130 ms 39000 KB Output is correct
13 Correct 124 ms 46164 KB Output is correct
14 Correct 60 ms 25168 KB Output is correct
15 Incorrect 62 ms 25228 KB Output isn't correct
16 Halted 0 ms 0 KB -