oj.uz

Submission #627207

# Submission time Handle Problem Language Result Execution time Memory
627207 2022-08-12T11:20:30 Z AA_Surely Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 96240 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;
int n, q, bad, cnt;
int head[N], ns[N], par[N], s[N], height[N];
int t[N][2];

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

    void build(int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) {
            tree[now] = s[ls];
            return;
        }

        int mid = (ls + rs) >> 1;
        build(lc, ls, mid);
        build(rc, mid + 1, rs);

        return;
    }

    void add(int lq, int rq, LL val, int now = 1, int ls = 0, int rs = n - 1) {
        //cout << "ls rs " << ls << ' ' << rs << endl;
        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];
    }

    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;
    //cout << "----------" << endl;
    val.add(0, 0, v0);
    //cout << "val.add(0, 0, " << v0 << ")" << endl;

    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) {
    par[now] = p;
    s[now] = 1;
    for(int on : adj[now]) if (on != p) {
        preD(on, now);
        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(now);
    LL sz_now = sz.get(now);
    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(v)) {
        int pl = active.rightest(t[v][0]);
        if (t[pl] >= t[ head[v] ]) v = pl;
        else v = par[ head[v] ];
    }

    return v;
}

void addUpTo(int v, int z, int x1, LL x2) {
    //cout << "z = " << z << endl;
    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];
        //cout << "v = " << v << endl;
    }

    return;
}

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

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

    updChoose(up);
    updChoose(v);

    active.change(v, 1);
    return;
}

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

    int sz_v = sz.get(v);
    int val_v = val.get(v);

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

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

    updChoose(up);
    remChoose(v);

    active.change(v, 0);
    return;
}

int main() {
    IOS;

    init();

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

    preD(0, n);
    precalc();
    dfs(0);
    sz.build();

    active.change(0, 1);
    fill(chs, chs + n, 1);
    updChoose(0);

    //cout << "val and size of 0 " << val.get(0) << ' ' << sz.get(0) << endl;

    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 235 ms 45964 KB Output is correct
2 Correct 214 ms 45952 KB Output is correct
3 Correct 220 ms 45988 KB Output is correct
4 Correct 210 ms 46000 KB Output is correct
5 Correct 191 ms 42060 KB Output is correct
6 Correct 19 ms 20392 KB Output is correct
7 Correct 23 ms 20216 KB Output is correct
8 Correct 17 ms 20272 KB Output is correct
9 Correct 180 ms 38324 KB Output is correct
10 Correct 212 ms 38248 KB Output is correct
11 Correct 239 ms 38364 KB Output is correct
12 Correct 209 ms 37472 KB Output is correct
13 Correct 211 ms 44432 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 19968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 42580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 45964 KB Output is correct
2 Correct 214 ms 45952 KB Output is correct
3 Correct 220 ms 45988 KB Output is correct
4 Correct 210 ms 46000 KB Output is correct
5 Correct 191 ms 42060 KB Output is correct
6 Correct 19 ms 20392 KB Output is correct
7 Correct 23 ms 20216 KB Output is correct
8 Correct 17 ms 20272 KB Output is correct
9 Correct 180 ms 38324 KB Output is correct
10 Correct 212 ms 38248 KB Output is correct
11 Correct 239 ms 38364 KB Output is correct
12 Correct 209 ms 37472 KB Output is correct
13 Correct 211 ms 44432 KB Output is correct
14 Execution timed out 3088 ms 19968 KB Time limit exceeded
15 Halted 0 ms 0 KB -