oj.uz

Submission #773920

# Submission time Handle Problem Language Result Execution time Memory
773920 2023-07-05T09:32:21 Z ParsaS Sumtree (INOI20_sumtree) C++17
30 / 100
 304 ms 92108 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 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 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);
    }
    int 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];
            }
            ans = 1LL * ans * binpow(F(u), MOD - 2) % MOD;
            c[u] -= c[v];
            f[u] += x - f[v];

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

            ans = 1LL * ans * F(u) % MOD * F(v) % MOD;
        }
        else {
            int u = par[v]; 
            while (val[u] == -1) {
                c[u] += c[v] + 1;
                f[u] += f[v] - val[v];
                u = par[u];
            }
            ans = 1LL * ans * binpow(1LL * F(v) * F(u) % MOD, MOD - 2) % MOD;
            //cout << " ! " << F(v) << ' ' << F(u) << endl;
            f[u] += f[v] - val[v];
            c[u] += c[v] + 1;
            c[v]++;
            val[v] = -1;

            ans = 1LL * ans * F(u) % MOD;
            //cout << "? " << c[u] << ' '<< f[u] << endl;
        }
        cout << ans << '\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 108 ms 53656 KB Output is correct
2 Correct 98 ms 53660 KB Output is correct
3 Correct 119 ms 53600 KB Output is correct
4 Correct 96 ms 53644 KB Output is correct
5 Correct 107 ms 49804 KB Output is correct
6 Correct 33 ms 35868 KB Output is correct
7 Correct 33 ms 35576 KB Output is correct
8 Correct 27 ms 35660 KB Output is correct
9 Correct 109 ms 46016 KB Output is correct
10 Correct 123 ms 45960 KB Output is correct
11 Correct 86 ms 45908 KB Output is correct
12 Correct 85 ms 45444 KB Output is correct
13 Correct 103 ms 52628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35464 KB Output is correct
2 Correct 26 ms 35532 KB Output is correct
3 Correct 31 ms 35504 KB Output is correct
4 Correct 26 ms 35508 KB Output is correct
5 Correct 26 ms 35528 KB Output is correct
6 Correct 27 ms 35680 KB Output is correct
7 Correct 26 ms 35632 KB Output is correct
8 Correct 26 ms 35644 KB Output is correct
9 Correct 27 ms 35756 KB Output is correct
10 Correct 27 ms 35748 KB Output is correct
11 Correct 32 ms 35836 KB Output is correct
12 Correct 26 ms 35748 KB Output is correct
13 Correct 27 ms 35788 KB Output is correct
14 Correct 27 ms 35732 KB Output is correct
15 Correct 27 ms 35956 KB Output is correct
16 Correct 30 ms 35656 KB Output is correct
17 Correct 28 ms 35788 KB Output is correct
18 Correct 29 ms 35764 KB Output is correct
19 Correct 30 ms 35752 KB Output is correct
20 Correct 28 ms 35624 KB Output is correct
21 Correct 29 ms 35616 KB Output is correct
22 Correct 30 ms 35540 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 53844 KB Output is correct
2 Correct 119 ms 54344 KB Output is correct
3 Correct 128 ms 54588 KB Output is correct
4 Correct 207 ms 55372 KB Output is correct
5 Correct 178 ms 53016 KB Output is correct
6 Correct 29 ms 35896 KB Output is correct
7 Correct 33 ms 35668 KB Output is correct
8 Correct 28 ms 35688 KB Output is correct
9 Correct 156 ms 48792 KB Output is correct
10 Correct 155 ms 48360 KB Output is correct
11 Correct 134 ms 48116 KB Output is correct
12 Runtime error 157 ms 92108 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 296 ms 50788 KB Output is correct
2 Correct 304 ms 50748 KB Output is correct
3 Correct 228 ms 50748 KB Output is correct
4 Correct 300 ms 50756 KB Output is correct
5 Correct 271 ms 50124 KB Output is correct
6 Correct 283 ms 50688 KB Output is correct
7 Correct 203 ms 44804 KB Output is correct
8 Correct 230 ms 44988 KB Output is correct
9 Correct 273 ms 50764 KB Output is correct
10 Correct 252 ms 50848 KB Output is correct
11 Correct 266 ms 50944 KB Output is correct
12 Correct 206 ms 45064 KB Output is correct
13 Incorrect 213 ms 43280 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 53656 KB Output is correct
2 Correct 98 ms 53660 KB Output is correct
3 Correct 119 ms 53600 KB Output is correct
4 Correct 96 ms 53644 KB Output is correct
5 Correct 107 ms 49804 KB Output is correct
6 Correct 33 ms 35868 KB Output is correct
7 Correct 33 ms 35576 KB Output is correct
8 Correct 27 ms 35660 KB Output is correct
9 Correct 109 ms 46016 KB Output is correct
10 Correct 123 ms 45960 KB Output is correct
11 Correct 86 ms 45908 KB Output is correct
12 Correct 85 ms 45444 KB Output is correct
13 Correct 103 ms 52628 KB Output is correct
14 Correct 25 ms 35464 KB Output is correct
15 Correct 26 ms 35532 KB Output is correct
16 Correct 31 ms 35504 KB Output is correct
17 Correct 26 ms 35508 KB Output is correct
18 Correct 26 ms 35528 KB Output is correct
19 Correct 27 ms 35680 KB Output is correct
20 Correct 26 ms 35632 KB Output is correct
21 Correct 26 ms 35644 KB Output is correct
22 Correct 27 ms 35756 KB Output is correct
23 Correct 27 ms 35748 KB Output is correct
24 Correct 32 ms 35836 KB Output is correct
25 Correct 26 ms 35748 KB Output is correct
26 Correct 27 ms 35788 KB Output is correct
27 Correct 27 ms 35732 KB Output is correct
28 Correct 27 ms 35956 KB Output is correct
29 Correct 30 ms 35656 KB Output is correct
30 Correct 28 ms 35788 KB Output is correct
31 Correct 29 ms 35764 KB Output is correct
32 Correct 30 ms 35752 KB Output is correct
33 Correct 28 ms 35624 KB Output is correct
34 Correct 29 ms 35616 KB Output is correct
35 Correct 30 ms 35540 KB Output is correct
36 Correct 118 ms 53844 KB Output is correct
37 Correct 119 ms 54344 KB Output is correct
38 Correct 128 ms 54588 KB Output is correct
39 Correct 207 ms 55372 KB Output is correct
40 Correct 178 ms 53016 KB Output is correct
41 Correct 29 ms 35896 KB Output is correct
42 Correct 33 ms 35668 KB Output is correct
43 Correct 28 ms 35688 KB Output is correct
44 Correct 156 ms 48792 KB Output is correct
45 Correct 155 ms 48360 KB Output is correct
46 Correct 134 ms 48116 KB Output is correct
47 Runtime error 157 ms 92108 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -