oj.uz

Submission #627095

# Submission time Handle Problem Language Result Execution time Memory
627095 2022-08-12T07:29:11 Z AA_Surely Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 51212 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], vir[N];
LL ns[N], n, q, bad, par[N], sz[N];
bool active[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--;
    
    val[v] += x;
    int now = par[v];
    while(!active[now]) {
        sz[now] -= sz[v];
        val[now] -= val[v];
        now = par[now];
    }

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

    updChoose(now);
    updChoose(v);

    active[v] = 1;
    return;
}

void remTag() {
    int v;
    cin >> v; 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] += val[v];

    val[v] -= vir[v];
    vir[v] = 0;

    updChoose(now);
    updChoose(v);

    active[v] = 0;
    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;

        /*cout << "after: " << endl;
        cout << "val: "; F0R(i, n) cout << val[i] << ' '; cout << endl;
        cout << "sz: "; F0R(i, n) cout << sz[i] << ' '; cout << endl;*/
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 38716 KB Output is correct
2 Correct 117 ms 38752 KB Output is correct
3 Correct 115 ms 38756 KB Output is correct
4 Correct 174 ms 38644 KB Output is correct
5 Correct 111 ms 34684 KB Output is correct
6 Correct 16 ms 20308 KB Output is correct
7 Correct 17 ms 20052 KB Output is correct
8 Correct 16 ms 20060 KB Output is correct
9 Correct 120 ms 31020 KB Output is correct
10 Correct 141 ms 31068 KB Output is correct
11 Correct 120 ms 31008 KB Output is correct
12 Correct 107 ms 30448 KB Output is correct
13 Correct 102 ms 37540 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 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 Correct 132 ms 41400 KB Output is correct
2 Correct 166 ms 44332 KB Output is correct
3 Correct 130 ms 44620 KB Output is correct
4 Correct 166 ms 45340 KB Output is correct
5 Correct 238 ms 43148 KB Output is correct
6 Correct 17 ms 20436 KB Output is correct
7 Correct 17 ms 20192 KB Output is correct
8 Correct 17 ms 20180 KB Output is correct
9 Correct 190 ms 38860 KB Output is correct
10 Correct 239 ms 38372 KB Output is correct
11 Correct 177 ms 38180 KB Output is correct
12 Correct 186 ms 38164 KB Output is correct
13 Execution timed out 3067 ms 51212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 38716 KB Output is correct
2 Correct 117 ms 38752 KB Output is correct
3 Correct 115 ms 38756 KB Output is correct
4 Correct 174 ms 38644 KB Output is correct
5 Correct 111 ms 34684 KB Output is correct
6 Correct 16 ms 20308 KB Output is correct
7 Correct 17 ms 20052 KB Output is correct
8 Correct 16 ms 20060 KB Output is correct
9 Correct 120 ms 31020 KB Output is correct
10 Correct 141 ms 31068 KB Output is correct
11 Correct 120 ms 31008 KB Output is correct
12 Correct 107 ms 30448 KB Output is correct
13 Correct 102 ms 37540 KB Output is correct
14 Incorrect 16 ms 19924 KB Output isn't correct
15 Halted 0 ms 0 KB -