oj.uz

Submission #587316

# Submission time Handle Problem Language Result Execution time Memory
587316 2022-07-01T16:09:15 Z lukameladze Sumtree (INOI20_sumtree) C++14
0 / 100
 110 ms 50924 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, mod = 1e9 + 7;
int t,n,a[N],fq[N],inv[N],cnt,r;
vector <int> v[N];
int f_p(int base, int power) {
	int result = 1;
	while (power > 0) {
		if (power % 2) result = (result * base) % mod;
		power /= 2;
		base = (base * base) % mod;
	}
	return result;
}
int C(int n, int k) {
	return (((fq[n] * inv[k])%mod) * inv[n - k]) % mod;
}
/*
*/
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>r;
    fq[0] = 1;
    for (int i = 1; i < N; i++) {
    	fq[i] = (fq[i - 1] * i)%mod;
	}
	inv[N - 1] = f_p(fq[N - 1], mod - 2);
	for (int i = N - 2; i > 1; i--) {
		inv[i] = (inv[i + 1] * (i + 1)) % mod;
	}
	inv[0] = 1;
    for (int i = 1; i <= n - 1; i++) {
    	int a, b;
    	cin>>a>>b;
    	v[a].pb(b);
    	v[b].pb(a);
	}
	cnt = n;
	for (int i = 1; i <= n; i++) {
		if (v[i].size() != 1 || i == 1) {
			// isn't leaf
			cnt++;
			v[i].pb(cnt);
			v[cnt].pb(i);
		}
	}
	n = cnt;
	int lf = 0;
	for (int i = 1; i <= n; i++) {
		if (i != 1 && v[i].size() == 1) lf++;
	}
	int q;
	cin>>q;
	cout<<C(r + lf - 1, lf - 1)<<"\n";
	/*
	
    
    
    
	*/
}

Compilation message

Main.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 49996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 50152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 50924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 49996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -