oj.uz

Submission #783973

# Submission time Handle Problem Language Result Execution time Memory
783973 2023-07-15T13:35:00 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 52132 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
vector<int>adj[maxn];
int n,q,mod=1e9+7,fact[maxn],revfact[maxn],val[maxn];
long long res=0;

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
 
void aval(){	
	fact[0]=1;
	for(long long i=1;i<maxn;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(long long i=maxn-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
 
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}

long long hes(long long a,long long b){
	a++;
	long long ret=c(b+a-1,a-1);	
	return ret;
}
long long ted[maxn],jam[maxn];

void solve(int u=1,int par=0){
	ted[u]=jam[u]=0;
	for(auto x:adj[u]){
		if(x!=par){
			solve(x,u);
			ted[u]+=ted[x];
			jam[u]+=jam[x];
		}
	}
	//cout<<u<<" "<<val[u]<<" "<<ted[u]<<" "<<jam[u]<<"\n";
	if(val[u]==-1){
		ted[u]++;
	}
	else{
		res*=hes(ted[u],val[u]-jam[u]);
		res%=mod;
		ted[u]=0;
		jam[u]=val[u];
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	int k;
	cin>>n;
	cin>>k;
	val[1]=k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=2;i<=n;i++){
		val[i]=-1;
	}
	res=1;
	solve();
	cout<<res<<"\n";
	cin>>q;
	for(int i=0;i<q;i++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,v;
			cin>>u>>v;
			val[u]=v;
		}
		else{
			int u;
			cin>>u;
			val[u]=-1;
		}
		res=1;
		solve();
		cout<<res<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 52044 KB Output is correct
2 Correct 103 ms 52132 KB Output is correct
3 Correct 105 ms 52124 KB Output is correct
4 Correct 129 ms 52044 KB Output is correct
5 Correct 107 ms 48176 KB Output is correct
6 Correct 37 ms 32000 KB Output is correct
7 Correct 35 ms 31756 KB Output is correct
8 Correct 33 ms 31788 KB Output is correct
9 Correct 100 ms 44456 KB Output is correct
10 Correct 99 ms 44364 KB Output is correct
11 Correct 105 ms 44448 KB Output is correct
12 Correct 115 ms 43708 KB Output is correct
13 Correct 99 ms 50756 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31584 KB Output is correct
2 Correct 33 ms 31564 KB Output is correct
3 Correct 33 ms 31644 KB Output is correct
4 Correct 33 ms 31632 KB Output is correct
5 Correct 37 ms 31640 KB Output is correct
6 Correct 77 ms 31732 KB Output is correct
7 Correct 74 ms 31692 KB Output is correct
8 Correct 74 ms 31700 KB Output is correct
9 Correct 141 ms 31756 KB Output is correct
10 Correct 151 ms 31984 KB Output is correct
11 Correct 147 ms 31980 KB Output is correct
12 Correct 40 ms 31856 KB Output is correct
13 Correct 147 ms 31888 KB Output is correct
14 Correct 152 ms 31920 KB Output is correct
15 Correct 169 ms 32084 KB Output is correct
16 Correct 157 ms 31760 KB Output is correct
17 Correct 170 ms 31892 KB Output is correct
18 Correct 84 ms 31848 KB Output is correct
19 Correct 141 ms 31876 KB Output is correct
20 Correct 75 ms 31700 KB Output is correct
21 Correct 102 ms 31780 KB Output is correct
22 Correct 44 ms 31592 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 51368 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 3060 ms 44724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 52044 KB Output is correct
2 Correct 103 ms 52132 KB Output is correct
3 Correct 105 ms 52124 KB Output is correct
4 Correct 129 ms 52044 KB Output is correct
5 Correct 107 ms 48176 KB Output is correct
6 Correct 37 ms 32000 KB Output is correct
7 Correct 35 ms 31756 KB Output is correct
8 Correct 33 ms 31788 KB Output is correct
9 Correct 100 ms 44456 KB Output is correct
10 Correct 99 ms 44364 KB Output is correct
11 Correct 105 ms 44448 KB Output is correct
12 Correct 115 ms 43708 KB Output is correct
13 Correct 99 ms 50756 KB Output is correct
14 Correct 33 ms 31584 KB Output is correct
15 Correct 33 ms 31564 KB Output is correct
16 Correct 33 ms 31644 KB Output is correct
17 Correct 33 ms 31632 KB Output is correct
18 Correct 37 ms 31640 KB Output is correct
19 Correct 77 ms 31732 KB Output is correct
20 Correct 74 ms 31692 KB Output is correct
21 Correct 74 ms 31700 KB Output is correct
22 Correct 141 ms 31756 KB Output is correct
23 Correct 151 ms 31984 KB Output is correct
24 Correct 147 ms 31980 KB Output is correct
25 Correct 40 ms 31856 KB Output is correct
26 Correct 147 ms 31888 KB Output is correct
27 Correct 152 ms 31920 KB Output is correct
28 Correct 169 ms 32084 KB Output is correct
29 Correct 157 ms 31760 KB Output is correct
30 Correct 170 ms 31892 KB Output is correct
31 Correct 84 ms 31848 KB Output is correct
32 Correct 141 ms 31876 KB Output is correct
33 Correct 75 ms 31700 KB Output is correct
34 Correct 102 ms 31780 KB Output is correct
35 Correct 44 ms 31592 KB Output is correct
36 Execution timed out 3059 ms 51368 KB Time limit exceeded
37 Halted 0 ms 0 KB -