oj.uz

Submission #627091

# Submission time Handle Problem Language Result Execution time Memory
627091 2022-08-12T07:17:10 Z AA_Surely Sumtree (INOI20_sumtree) C++14
10 / 100
 178 ms 39740 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 5e5 + 7;
const int LOG = 22;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

LL fact[N], ifact[N];
LL chs[N], ans, val[N];
bool active[N];
LL ns[N], n, q, bad, par[N], sz[N];
VI adj[N];

#define endl '\n'

inline int pw(LL a, int b) {
    LL ret = 1;
    for(; b; b >>= 1, a = a * a % MOD)
        if (b & 1) ret = ret * a % MOD;
    return ret;
}

void precalc() {
    fact[0] = 1;
    FOR(i, 1, N) fact[i] = fact[i - 1] * i % MOD;
    ifact[N - 1] = pw(fact[N - 1], MOD - 2);
    R0F(i, N - 1) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
    return;
}

inline int nCr(int nn, int rr) {
    if (nn < rr || rr < 0) return 0;
    return (fact[nn] * ifact[rr] % MOD) * ifact[nn - rr] % MOD;
}

void init() {
    cin >> n >> val[0];
    F0R(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[--u].PB(--v);
        adj[v].PB(u);
    }

    cin >> q;
    return;
}

void dfs(int now, int p) {
    par[now] = p;
    sz[now] = 1;
    for(int on : adj[now]) if (on != p) {
        dfs(on, now);
        sz[now] += sz[on];
    }
    return;
}

void updChoose(int now) {
    if (!chs[now]) bad--;
    else ans = (ans * pw(chs[now], MOD - 2)) % MOD;

    chs[now] = nCr(val[now] + sz[now] - 1, sz[now] - 1);

    if (!chs[now]) bad++;
    else ans = (ans * chs[now]) % MOD;

    return;
}

void addTag() {
    int v, x;
    cin >> v >> x;
    v--;
    
    int now = par[v];
    while(!active[now]) {
        sz[now] -= sz[v];
        val[now] -= val[v];
        now = par[now];
    }

    sz[now] -= sz[v];
    val[now] -= x;
    val[v] += x;

    updChoose(now);
    updChoose(v);

    active[v] = 1;
    return;
}

int main() {
    IOS;

    init();
    precalc();
    dfs(0, -1);

    active[0] = 1;
    fill(chs, chs + n, 1);
    chs[0] = nCr(val[0] + n - 1, n - 1);
    ans = chs[0];

    cout << ans << endl;

    while(q--) {
        int tp; cin >> tp;
        if (tp == 1) addTag();
        //else remTag();

        cout << (bad ? 0 : ans) << endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 38708 KB Output is correct
2 Correct 127 ms 38752 KB Output is correct
3 Correct 128 ms 38660 KB Output is correct
4 Correct 117 ms 38744 KB Output is correct
5 Correct 103 ms 34736 KB Output is correct
6 Correct 16 ms 20300 KB Output is correct
7 Correct 16 ms 20052 KB Output is correct
8 Correct 16 ms 20052 KB Output is correct
9 Correct 138 ms 31116 KB Output is correct
10 Correct 135 ms 31024 KB Output is correct
11 Correct 127 ms 31060 KB Output is correct
12 Correct 116 ms 30552 KB Output is correct
13 Correct 137 ms 37580 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 38708 KB Output is correct
2 Correct 127 ms 38752 KB Output is correct
3 Correct 128 ms 38660 KB Output is correct
4 Correct 117 ms 38744 KB Output is correct
5 Correct 103 ms 34736 KB Output is correct
6 Correct 16 ms 20300 KB Output is correct
7 Correct 16 ms 20052 KB Output is correct
8 Correct 16 ms 20052 KB Output is correct
9 Correct 138 ms 31116 KB Output is correct
10 Correct 135 ms 31024 KB Output is correct
11 Correct 127 ms 31060 KB Output is correct
12 Correct 116 ms 30552 KB Output is correct
13 Correct 137 ms 37580 KB Output is correct
14 Incorrect 15 ms 19924 KB Output isn't correct
15 Halted 0 ms 0 KB -