oj.uz

Submission #999092

# Submission time Handle Problem Language Result Execution time Memory
999092 2024-06-15T06:28:08 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 369 ms 47036 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 q; cin >> q;
    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;
    }
    for(int i = 0; i <= r; i++){
        ans = (ans + Cnk(i + n - 2, n - 2)) % MOD;
    }
    cout << ans << '\n';
}   

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 46740 KB Output is correct
2 Correct 364 ms 46760 KB Output is correct
3 Correct 359 ms 46672 KB Output is correct
4 Correct 361 ms 46664 KB Output is correct
5 Correct 360 ms 45648 KB Output is correct
6 Correct 325 ms 39420 KB Output is correct
7 Correct 323 ms 39452 KB Output is correct
8 Correct 318 ms 39508 KB Output is correct
9 Correct 367 ms 47036 KB Output is correct
10 Correct 365 ms 46776 KB Output is correct
11 Correct 369 ms 46928 KB Output is correct
12 Correct 360 ms 46676 KB Output is correct
13 Correct 356 ms 46164 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 315 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 46692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 46740 KB Output is correct
2 Correct 364 ms 46760 KB Output is correct
3 Correct 359 ms 46672 KB Output is correct
4 Correct 361 ms 46664 KB Output is correct
5 Correct 360 ms 45648 KB Output is correct
6 Correct 325 ms 39420 KB Output is correct
7 Correct 323 ms 39452 KB Output is correct
8 Correct 318 ms 39508 KB Output is correct
9 Correct 367 ms 47036 KB Output is correct
10 Correct 365 ms 46776 KB Output is correct
11 Correct 369 ms 46928 KB Output is correct
12 Correct 360 ms 46676 KB Output is correct
13 Correct 356 ms 46164 KB Output is correct
14 Incorrect 315 ms 39504 KB Output isn't correct
15 Halted 0 ms 0 KB -