oj.uz

Submission #627090

# Submission time Handle Problem Language Result Execution time Memory
627090 2022-08-12T07:02:22 Z AA_Surely Sumtree (INOI20_sumtree) C++14
10 / 100
 189 ms 40608 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;

#define endl '\n'

LL fact[N], ifact[N];
LL chs[N], ans, val[N];
bool active[N];
int ns[N], n, q, bad, par[N], sz[N];
VI adj[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 >> ns[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];
        now = par[now];
    }

    sz[now] -= sz[v];
    val[now] -= 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(ns[0] + n - 1, n - 1);
    ans = chs[0];
    val[0] = ns[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 121 ms 39584 KB Output is correct
2 Correct 121 ms 39640 KB Output is correct
3 Correct 119 ms 39632 KB Output is correct
4 Correct 120 ms 39512 KB Output is correct
5 Correct 111 ms 35656 KB Output is correct
6 Correct 19 ms 20308 KB Output is correct
7 Correct 17 ms 20088 KB Output is correct
8 Correct 16 ms 20144 KB Output is correct
9 Correct 116 ms 31976 KB Output is correct
10 Correct 118 ms 31820 KB Output is correct
11 Correct 118 ms 31928 KB Output is correct
12 Correct 111 ms 31232 KB Output is correct
13 Correct 101 ms 38392 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 39584 KB Output is correct
2 Correct 121 ms 39640 KB Output is correct
3 Correct 119 ms 39632 KB Output is correct
4 Correct 120 ms 39512 KB Output is correct
5 Correct 111 ms 35656 KB Output is correct
6 Correct 19 ms 20308 KB Output is correct
7 Correct 17 ms 20088 KB Output is correct
8 Correct 16 ms 20144 KB Output is correct
9 Correct 116 ms 31976 KB Output is correct
10 Correct 118 ms 31820 KB Output is correct
11 Correct 118 ms 31928 KB Output is correct
12 Correct 111 ms 31232 KB Output is correct
13 Correct 101 ms 38392 KB Output is correct
14 Incorrect 16 ms 19952 KB Output isn't correct
15 Halted 0 ms 0 KB -