oj.uz

Submission #999040

# Submission time Handle Problem Language Result Execution time Memory
999040 2024-06-15T05:33:14 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 63 ms 41640 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 1e6 + 5;
const int mod = 1e9 + 7;

int n, r;
vector<int> adj[MXN];
int f[MXN];

int pw(int a, int b, int c)
{
	a %= c;
	int res = 1;
	while (b)
	{
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

int nck(int n, int k)
{
	if (min(n, k) < 0 || k > n) return 0;
	return (f[n] * pw((f[n - k] * f[k]) % mod, mod - 2, mod)) % mod;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	f[0] = 1;
	for (int i = 1; i < MXN; i++) f[i] = (f[i - 1] * i) % mod;
	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);
	}
	int q, res = 0;
	cin >> q;
	cout << nck(n + r - 1, r) << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:47:9: warning: unused variable 'res' [-Wunused-variable]
   47 |  int q, res = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 38996 KB Output is correct
2 Correct 63 ms 41300 KB Output is correct
3 Correct 58 ms 41296 KB Output is correct
4 Correct 53 ms 41300 KB Output is correct
5 Correct 52 ms 40528 KB Output is correct
6 Correct 10 ms 31836 KB Output is correct
7 Correct 10 ms 31788 KB Output is correct
8 Correct 10 ms 31836 KB Output is correct
9 Correct 57 ms 41640 KB Output is correct
10 Correct 59 ms 41556 KB Output is correct
11 Correct 53 ms 41556 KB Output is correct
12 Correct 53 ms 41040 KB Output is correct
13 Correct 49 ms 40484 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 38996 KB Output is correct
2 Correct 63 ms 41300 KB Output is correct
3 Correct 58 ms 41296 KB Output is correct
4 Correct 53 ms 41300 KB Output is correct
5 Correct 52 ms 40528 KB Output is correct
6 Correct 10 ms 31836 KB Output is correct
7 Correct 10 ms 31788 KB Output is correct
8 Correct 10 ms 31836 KB Output is correct
9 Correct 57 ms 41640 KB Output is correct
10 Correct 59 ms 41556 KB Output is correct
11 Correct 53 ms 41556 KB Output is correct
12 Correct 53 ms 41040 KB Output is correct
13 Correct 49 ms 40484 KB Output is correct
14 Incorrect 9 ms 31576 KB Output isn't correct
15 Halted 0 ms 0 KB -