oj.uz

Submission #587317

# Submission time Handle Problem Language Result Execution time Memory
587317 2022-07-01T16:09:59 Z lukameladze Sumtree (INOI20_sumtree) C++14
10 / 100
 141 ms 37960 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 = 5e5 + 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 32460 KB Output is correct
2 Correct 131 ms 34992 KB Output is correct
3 Correct 120 ms 34928 KB Output is correct
4 Correct 121 ms 34920 KB Output is correct
5 Correct 113 ms 37960 KB Output is correct
6 Correct 18 ms 20052 KB Output is correct
7 Correct 19 ms 20052 KB Output is correct
8 Correct 17 ms 20016 KB Output is correct
9 Correct 123 ms 34104 KB Output is correct
10 Correct 111 ms 34088 KB Output is correct
11 Correct 121 ms 34160 KB Output is correct
12 Correct 134 ms 33532 KB Output is correct
13 Correct 140 ms 33572 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 32460 KB Output is correct
2 Correct 131 ms 34992 KB Output is correct
3 Correct 120 ms 34928 KB Output is correct
4 Correct 121 ms 34920 KB Output is correct
5 Correct 113 ms 37960 KB Output is correct
6 Correct 18 ms 20052 KB Output is correct
7 Correct 19 ms 20052 KB Output is correct
8 Correct 17 ms 20016 KB Output is correct
9 Correct 123 ms 34104 KB Output is correct
10 Correct 111 ms 34088 KB Output is correct
11 Correct 121 ms 34160 KB Output is correct
12 Correct 134 ms 33532 KB Output is correct
13 Correct 140 ms 33572 KB Output is correct
14 Incorrect 16 ms 19796 KB Output isn't correct
15 Halted 0 ms 0 KB -