oj.uz

Submission #935501

# Submission time Handle Problem Language Result Execution time Memory
935501 2024-02-29T08:16:28 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 47012 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=0,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);
		mize[z]=mark[z];
		sz[z]=0;
	}
	//cout<<z<<" "<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	fuck[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=0;
		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 144 ms 46996 KB Output is correct
2 Correct 149 ms 47012 KB Output is correct
3 Correct 134 ms 46968 KB Output is correct
4 Correct 137 ms 47004 KB Output is correct
5 Correct 123 ms 42836 KB Output is correct
6 Correct 61 ms 25500 KB Output is correct
7 Correct 61 ms 25424 KB Output is correct
8 Correct 62 ms 25504 KB Output is correct
9 Correct 164 ms 39248 KB Output is correct
10 Correct 130 ms 39328 KB Output is correct
11 Correct 136 ms 39252 KB Output is correct
12 Correct 136 ms 39072 KB Output is correct
13 Correct 130 ms 46232 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 25232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3025 ms 46864 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 3017 ms 39764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 46996 KB Output is correct
2 Correct 149 ms 47012 KB Output is correct
3 Correct 134 ms 46968 KB Output is correct
4 Correct 137 ms 47004 KB Output is correct
5 Correct 123 ms 42836 KB Output is correct
6 Correct 61 ms 25500 KB Output is correct
7 Correct 61 ms 25424 KB Output is correct
8 Correct 62 ms 25504 KB Output is correct
9 Correct 164 ms 39248 KB Output is correct
10 Correct 130 ms 39328 KB Output is correct
11 Correct 136 ms 39252 KB Output is correct
12 Correct 136 ms 39072 KB Output is correct
13 Correct 130 ms 46232 KB Output is correct
14 Incorrect 61 ms 25232 KB Output isn't correct
15 Halted 0 ms 0 KB -