oj.uz

Submission #999100

# Submission time Handle Problem Language Result Execution time Memory
999100 2024-06-15T06:35:59 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 369 ms 46932 KB 
#include <bits/stdc++.h>

#define int long long
// #define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 1e6 + 5, LOGMAX = 20, B = 800, MOD = 1e9 + 7;

// int tree[4 * MAX], lazy[4 * MAX];

// void relax(int node, int l, int r){
//     if(!lazy[node]) return;
//     tree[node] += lazy[node];
//     if(l != r){
//         lazy[2 * node] += lazy[node];
//         lazy[2 * node + 1] += lazy[node];
//     }
//     lazy[node] = 0;
// }

// void update(int node, int l, int r, int ul, int ur, int val){
//     relax(node, l, r);
//     if(ur < l || r < ul) return;
//     if(ul <= l && r <= ur){
//         lazy[node] += val;
//         relax(node, l, r);
//         return;
//     }
//     int mid = (l + r) / 2;
//     update(2 * node, l, mid, ul, ur, val);
//     update(2 * node + 1, mid + 1, r, ul, ur, val);
//     tree[node] = max(tree[2 * node], tree[2 * node + 1]);
// }

// int ask(int node, int l, int r, int ql, int qr){
//     if(qr < l || r < ql) return 0;
//     relax(node, l, r);
//     if(ql <= l && r <= qr) return tree[node];
//     int mid = (l + r) / 2;
//     return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
// }

int f[MAX];
int invf[MAX];

int Cnk(int n, int k){
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}

int binpow(int a, int b){
    if(b == 0) return 1;
    if(b & 1) return binpow(a, b - 1) % MOD * a % MOD;
    else return binpow(a * a % MOD, b / 2) % MOD;
}
int inv(int a){
    return binpow(a, MOD - 2);
}

vector<int> g[MAX];

void solve(){
    int n, r; cin >> n >> r;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    f[0] = 1;
    invf[0] = 1;
    for(int i = 1; i < MAX; i++){
        f[i] = f[i - 1] * i % MOD;
        invf[i] = invf[i - 1] * inv(i) % MOD;
    }
    int q; cin >> q;
    cout << Cnk(r + n - 1, n - 1) << '\n';
}   

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--) solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:70:9: warning: unused variable 'ans' [-Wunused-variable]
   70 |     int ans = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 46676 KB Output is correct
2 Correct 369 ms 46672 KB Output is correct
3 Correct 367 ms 46672 KB Output is correct
4 Correct 366 ms 46676 KB Output is correct
5 Correct 366 ms 45652 KB Output is correct
6 Correct 317 ms 39504 KB Output is correct
7 Correct 316 ms 39436 KB Output is correct
8 Correct 316 ms 39452 KB Output is correct
9 Correct 362 ms 46808 KB Output is correct
10 Correct 359 ms 46932 KB Output is correct
11 Correct 366 ms 46824 KB Output is correct
12 Correct 359 ms 46448 KB Output is correct
13 Correct 357 ms 45908 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 46676 KB Output is correct
2 Correct 369 ms 46672 KB Output is correct
3 Correct 367 ms 46672 KB Output is correct
4 Correct 366 ms 46676 KB Output is correct
5 Correct 366 ms 45652 KB Output is correct
6 Correct 317 ms 39504 KB Output is correct
7 Correct 316 ms 39436 KB Output is correct
8 Correct 316 ms 39452 KB Output is correct
9 Correct 362 ms 46808 KB Output is correct
10 Correct 359 ms 46932 KB Output is correct
11 Correct 366 ms 46824 KB Output is correct
12 Correct 359 ms 46448 KB Output is correct
13 Correct 357 ms 45908 KB Output is correct
14 Incorrect 317 ms 39504 KB Output isn't correct
15 Halted 0 ms 0 KB -