oj.uz

Submission #627296

# Submission time Handle Problem Language Result Execution time Memory
627296 2022-08-12T12:06:10 Z AA_Surely Sumtree (INOI20_sumtree) C++14
10 / 100
 737 ms 104760 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 lc now << 1
#define rc now << 1 | 1
#define endl '\n'

LL chs[N], vir[N], fact[N], ifact[N];
LL ans;
VI adj[N], order;
LL n, q, bad, cnt;
LL head[N], par[N], s[N], height[N];
LL t[N][2];

struct SumTree {
    LL tree[N << 2];

    void add(int lq, int rq, LL val, int now = 1, int ls = 0, int rs = n - 1) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) {
            tree[now] += val;
            return;
        }

        int mid = (ls + rs) >> 1;
        add(lq, rq, val, lc, ls, mid);
        add(lq, rq, val, rc, mid + 1, rs);

        return;
    }

    LL get(int id, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) return tree[now];
        int mid = (ls + rs) >> 1;
        if (id <= mid) return get(id, lc, ls, mid) + tree[now];
        return get(id, rc, mid + 1, rs) + tree[now];
    }
} val, sz;

struct DescendTree {
    bool tree[N << 2];
    bool arr[N];

    void ch(int id, bool val, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) {
            tree[now] = val;
            return;
        }

        int mid = (ls + rs) >> 1;
        if (ls <= mid) ch(id, val, lc, ls, mid);
        else ch(id, val, rc, mid + 1, rs);

        tree[now] = tree[lc] | tree[rc];
        return;
    }

    void change(int id, int val) {
        ch(id, val);
        arr[id] = val;
    }

    int g(int x) {
        return arr[x];
    }

    int rightest(int q, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls > q || !tree[now]) return n;
        if (ls == rs) return ls;
        int mid = (ls + rs) >> 1;
        int case1 = rightest(q, rc, mid + 1, rs);
        return (case1 == n ? rightest(q, lc, ls, mid) : case1);
    }
} active;

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;
}

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() {
    LL v0;
    cin >> n >> v0;
    val.add(0, 0, v0);

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

    cin >> q;

    ans = 1;
    return;
}

void preD(int now, int p, int h = 0) {
    par[now] = p;
    s[now] = 1;
    height[now] = h;
    for(int on : adj[now]) if (on != p) {
        preD(on, now, h + 1);
        s[now] += s[on];
    }
    return;
}

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;

    iota(head, head + n, 0);

    F0R(i, n) {
        sort(ALL(adj[i]), [](const int &a, const int &b) {return s[a] < s[b];});
        if (i) adj[i].pop_back();
        reverse(ALL(adj[i]));
    }

    return;
}

void dfs(int now) {
    order.PB(now);
    t[now][0] = cnt++;
    if (!adj[now].empty()) head[ adj[now][0] ] = head[now];

    for(int on : adj[now]) dfs(on);

    t[now][1] = cnt;
    return;
}

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

    LL val_now = val.get(t[now][0]);
    LL sz_now = sz.get(t[now][0]);
    chs[now] = nCr(val_now + sz_now - 1, sz_now - 1);

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

    return;
}

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

    chs[now] = 1;

    return;
}

int getUpperActive(int v) {
    while(!active.g(t[v][0])) {
        int pl = order[ active.rightest(t[v][0]) ];
        assert(pl != n);
        if (t[pl][0] >= t[ head[v] ][0]) v = pl;
        else v = par[ head[v] ];
    }

    return v;
}

void addUpTo(int v, int z, LL x1, LL x2) {
    while(height[v] >= height[z]) {
        int w = (height[ head[v] ] >= height[z] ? head[v] : z);
        sz.add(t[w][0], t[v][0], x1);
        val.add(t[w][0], t[v][0], x2);

        v = par[w];
    }

    return;
}

void addTag() {
    int v, x;
    cin >> v >> x;
    v--;
    
    val.add(t[v][0], t[v][0], x);
    LL sz_v = sz.get(t[v][0]);
    LL val_v = val.get(t[v][0]);

    int up = getUpperActive(v);
    addUpTo(par[v], up, -sz_v, -val_v);
    
    vir[v] = x;

    updChoose(up);
    updChoose(v);

    active.change(t[v][0], 1);
    return;
}

void remTag() {
    int v;
    cin >> v; 
    v--;

    LL sz_v = sz.get(t[v][0]);
    LL val_v = val.get(t[v][0]);

    int up = getUpperActive(par[v]);
    addUpTo(par[v], up, sz_v, val_v);

    val.add(t[v][0], t[v][0], -vir[v]);

    updChoose(up);
    remChoose(v);

    active.change(t[v][0], 0);
    return;
}

int main() {
    IOS;

    init();

    height[n] = -1;
    par[0] = n;

    preD(0, n);
    precalc();
    dfs(0);

    F0R(i, n) sz.add(t[i][0], t[i][0], s[i]);

    active.change(0, 1);
    fill(chs, chs + n, 1);
    updChoose(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 168 ms 49088 KB Output is correct
2 Correct 171 ms 48972 KB Output is correct
3 Correct 186 ms 48992 KB Output is correct
4 Correct 178 ms 49000 KB Output is correct
5 Correct 150 ms 45012 KB Output is correct
6 Correct 18 ms 20540 KB Output is correct
7 Correct 17 ms 20212 KB Output is correct
8 Correct 17 ms 20320 KB Output is correct
9 Correct 177 ms 41452 KB Output is correct
10 Correct 180 ms 41316 KB Output is correct
11 Correct 186 ms 41312 KB Output is correct
12 Correct 181 ms 40484 KB Output is correct
13 Correct 160 ms 47204 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 104760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 49088 KB Output is correct
2 Correct 171 ms 48972 KB Output is correct
3 Correct 186 ms 48992 KB Output is correct
4 Correct 178 ms 49000 KB Output is correct
5 Correct 150 ms 45012 KB Output is correct
6 Correct 18 ms 20540 KB Output is correct
7 Correct 17 ms 20212 KB Output is correct
8 Correct 17 ms 20320 KB Output is correct
9 Correct 177 ms 41452 KB Output is correct
10 Correct 180 ms 41316 KB Output is correct
11 Correct 186 ms 41312 KB Output is correct
12 Correct 181 ms 40484 KB Output is correct
13 Correct 160 ms 47204 KB Output is correct
14 Correct 15 ms 19924 KB Output is correct
15 Incorrect 15 ms 19852 KB Output isn't correct
16 Halted 0 ms 0 KB -