oj.uz

Submission #470136

# Submission time Handle Problem Language Result Execution time Memory
470136 2021-09-03T05:26:41 Z Sohsoh84 Sumtree (INOI20_sumtree) C++14
10 / 100
 292 ms 48652 KB 
// orz
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}

	return ans;
}

int n, r, q;
ll fact[MAXN], inv[MAXN];
vector<int> adj[MAXN];

inline ll C(ll k, ll n) {
	if (k < 0 || k > n) return 0;
	return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fact[0] = inv[0] = 1;
	for (int i = 1; i < MAXN; i++) 
		fact[i] = fact[i - 1] * i % MOD, inv[i] = poww(fact[i], MOD - 2);

	cin >> n >> r;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}

	cout << C(n - 1, r + n - 1) << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 48072 KB Output is correct
2 Correct 292 ms 48136 KB Output is correct
3 Correct 281 ms 48112 KB Output is correct
4 Correct 284 ms 48164 KB Output is correct
5 Correct 263 ms 48196 KB Output is correct
6 Correct 173 ms 39440 KB Output is correct
7 Correct 174 ms 39548 KB Output is correct
8 Correct 171 ms 39508 KB Output is correct
9 Correct 270 ms 48324 KB Output is correct
10 Correct 271 ms 48224 KB Output is correct
11 Correct 271 ms 48220 KB Output is correct
12 Correct 270 ms 47764 KB Output is correct
13 Correct 260 ms 47172 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 48072 KB Output is correct
2 Correct 292 ms 48136 KB Output is correct
3 Correct 281 ms 48112 KB Output is correct
4 Correct 284 ms 48164 KB Output is correct
5 Correct 263 ms 48196 KB Output is correct
6 Correct 173 ms 39440 KB Output is correct
7 Correct 174 ms 39548 KB Output is correct
8 Correct 171 ms 39508 KB Output is correct
9 Correct 270 ms 48324 KB Output is correct
10 Correct 271 ms 48224 KB Output is correct
11 Correct 271 ms 48220 KB Output is correct
12 Correct 270 ms 47764 KB Output is correct
13 Correct 260 ms 47172 KB Output is correct
14 Incorrect 169 ms 39368 KB Output isn't correct
15 Halted 0 ms 0 KB -