oj.uz

Submission #773934

# Submission time Handle Problem Language Result Execution time Memory
773934 2023-07-05T09:44:52 Z ParsaS Sumtree (INOI20_sumtree) C++17
30 / 100
 347 ms 92084 KB 
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, r;
int fact[N], inv[N], f[N], c[N];
int val[N], par[N];
vector<int> adj[N];
int ans, bad;

int binpow(int a, int b) {
    return b ? 1LL * binpow(1LL * a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD : 1;
}
int C(int a, int b) {
    return 1LL * fact[b] * inv[a] % MOD * inv[b - a] % MOD;
}
void dfs(int v, int p) {
    c[v] = 1;
    par[v] = p;
    for (auto u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            c[v] += c[u];
        }
    }
}
int F(int v) {
    return C(c[v], val[v] - f[v] + c[v]);
} 
void add(int v) {
    if (F(v) == 0)
        bad++;
    else
        ans = 1LL * ans * F(v) % MOD;
}
void rem(int v) {
    if (F(v) == 0)
        bad--;
    else
        ans = 1LL * ans * binpow(F(v), MOD - 2) % MOD;
}

void solve() {
    cin >> n >> r;
    for (int i = 0; i < n - 1; i++) {
        int v, u; cin >> v >> u;
        adj[v].pb(u), adj[u].pb(v);
    }
    ans = C(n - 1, r + n - 1);
    val[1] = r;
    dfs(1, 0);
    c[1]--;
    cout << ans << '\n';

    int q; cin >> q;
    memset(val, -1, sizeof val);
    val[1] = r;
    while (q--) {
        int t, v; cin >> t >> v;
        if (t == 1) {
            int x; cin >> x;
            int u = par[v];
            while (val[u] == -1) {
                c[u] -= c[v];
                f[u] += x - f[v];
                u = par[u];
            }
            rem(u);
            c[u] -= c[v];
            f[u] += x - f[v];

            c[v]--;
            val[v] = x;

            add(u);
            add(v);
        }
        else {
            int u = par[v]; 
            while (val[u] == -1) {
                c[u] += c[v] + 1;
                f[u] += f[v] - val[v];
                u = par[u];
            }
            rem(v);
            rem(u);
            //cout << " ! " << F(v) << ' ' << F(u) << endl;
            f[u] += f[v] - val[v];
            c[u] += c[v] + 1;
            c[v]++;
            val[v] = -1;

            add(u);
        }
        if (bad == 0)
            cout << ans << '\n';
        else
            cout << 0 << '\n';
    }
}

int32_t main() {
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = 1LL * i * fact[i - 1] % MOD;
    inv[N - 1] = binpow(fact[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = 1LL * inv[i + 1] * (i + 1) % MOD;
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 53644 KB Output is correct
2 Correct 100 ms 53580 KB Output is correct
3 Correct 95 ms 53640 KB Output is correct
4 Correct 102 ms 53648 KB Output is correct
5 Correct 89 ms 49696 KB Output is correct
6 Correct 33 ms 35836 KB Output is correct
7 Correct 30 ms 35684 KB Output is correct
8 Correct 29 ms 35600 KB Output is correct
9 Correct 92 ms 46012 KB Output is correct
10 Correct 94 ms 45888 KB Output is correct
11 Correct 105 ms 45940 KB Output is correct
12 Correct 99 ms 45468 KB Output is correct
13 Correct 92 ms 52516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35540 KB Output is correct
2 Correct 31 ms 35560 KB Output is correct
3 Correct 26 ms 35532 KB Output is correct
4 Correct 29 ms 35472 KB Output is correct
5 Correct 31 ms 35484 KB Output is correct
6 Correct 27 ms 35616 KB Output is correct
7 Correct 27 ms 35608 KB Output is correct
8 Correct 27 ms 35656 KB Output is correct
9 Correct 29 ms 35708 KB Output is correct
10 Correct 29 ms 35740 KB Output is correct
11 Correct 29 ms 35728 KB Output is correct
12 Correct 27 ms 35720 KB Output is correct
13 Correct 34 ms 35720 KB Output is correct
14 Correct 29 ms 35808 KB Output is correct
15 Correct 36 ms 35892 KB Output is correct
16 Correct 30 ms 35740 KB Output is correct
17 Correct 33 ms 35756 KB Output is correct
18 Correct 29 ms 35668 KB Output is correct
19 Correct 29 ms 35716 KB Output is correct
20 Correct 28 ms 35652 KB Output is correct
21 Correct 28 ms 35620 KB Output is correct
22 Correct 28 ms 35540 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 53840 KB Output is correct
2 Correct 120 ms 54340 KB Output is correct
3 Correct 118 ms 54488 KB Output is correct
4 Correct 159 ms 55104 KB Output is correct
5 Correct 170 ms 51788 KB Output is correct
6 Correct 31 ms 35924 KB Output is correct
7 Correct 31 ms 35644 KB Output is correct
8 Correct 30 ms 35672 KB Output is correct
9 Correct 194 ms 47984 KB Output is correct
10 Correct 164 ms 47812 KB Output is correct
11 Correct 152 ms 47724 KB Output is correct
12 Runtime error 140 ms 92084 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 48860 KB Output is correct
2 Correct 304 ms 48864 KB Output is correct
3 Correct 267 ms 48820 KB Output is correct
4 Correct 347 ms 48900 KB Output is correct
5 Correct 290 ms 48476 KB Output is correct
6 Correct 310 ms 49000 KB Output is correct
7 Correct 211 ms 44548 KB Output is correct
8 Correct 230 ms 44620 KB Output is correct
9 Correct 297 ms 48896 KB Output is correct
10 Correct 275 ms 48964 KB Output is correct
11 Correct 273 ms 48956 KB Output is correct
12 Correct 260 ms 44636 KB Output is correct
13 Incorrect 187 ms 42812 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 53644 KB Output is correct
2 Correct 100 ms 53580 KB Output is correct
3 Correct 95 ms 53640 KB Output is correct
4 Correct 102 ms 53648 KB Output is correct
5 Correct 89 ms 49696 KB Output is correct
6 Correct 33 ms 35836 KB Output is correct
7 Correct 30 ms 35684 KB Output is correct
8 Correct 29 ms 35600 KB Output is correct
9 Correct 92 ms 46012 KB Output is correct
10 Correct 94 ms 45888 KB Output is correct
11 Correct 105 ms 45940 KB Output is correct
12 Correct 99 ms 45468 KB Output is correct
13 Correct 92 ms 52516 KB Output is correct
14 Correct 27 ms 35540 KB Output is correct
15 Correct 31 ms 35560 KB Output is correct
16 Correct 26 ms 35532 KB Output is correct
17 Correct 29 ms 35472 KB Output is correct
18 Correct 31 ms 35484 KB Output is correct
19 Correct 27 ms 35616 KB Output is correct
20 Correct 27 ms 35608 KB Output is correct
21 Correct 27 ms 35656 KB Output is correct
22 Correct 29 ms 35708 KB Output is correct
23 Correct 29 ms 35740 KB Output is correct
24 Correct 29 ms 35728 KB Output is correct
25 Correct 27 ms 35720 KB Output is correct
26 Correct 34 ms 35720 KB Output is correct
27 Correct 29 ms 35808 KB Output is correct
28 Correct 36 ms 35892 KB Output is correct
29 Correct 30 ms 35740 KB Output is correct
30 Correct 33 ms 35756 KB Output is correct
31 Correct 29 ms 35668 KB Output is correct
32 Correct 29 ms 35716 KB Output is correct
33 Correct 28 ms 35652 KB Output is correct
34 Correct 28 ms 35620 KB Output is correct
35 Correct 28 ms 35540 KB Output is correct
36 Correct 116 ms 53840 KB Output is correct
37 Correct 120 ms 54340 KB Output is correct
38 Correct 118 ms 54488 KB Output is correct
39 Correct 159 ms 55104 KB Output is correct
40 Correct 170 ms 51788 KB Output is correct
41 Correct 31 ms 35924 KB Output is correct
42 Correct 31 ms 35644 KB Output is correct
43 Correct 30 ms 35672 KB Output is correct
44 Correct 194 ms 47984 KB Output is correct
45 Correct 164 ms 47812 KB Output is correct
46 Correct 152 ms 47724 KB Output is correct
47 Runtime error 140 ms 92084 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -