oj.uz

Submission #627292

# Submission time Handle Problem Language Result Execution time Memory
627292 2022-08-12T11:58:28 Z AA_Surely Sumtree (INOI20_sumtree) C++14
30 / 100
 3000 ms 59896 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]) ];
        if (t[pl] >= t[ head[v] ]) 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 194 ms 49028 KB Output is correct
2 Correct 184 ms 49080 KB Output is correct
3 Correct 196 ms 49108 KB Output is correct
4 Correct 223 ms 49040 KB Output is correct
5 Correct 166 ms 45120 KB Output is correct
6 Correct 18 ms 20532 KB Output is correct
7 Correct 18 ms 20300 KB Output is correct
8 Correct 19 ms 20356 KB Output is correct
9 Correct 234 ms 41464 KB Output is correct
10 Correct 225 ms 41284 KB Output is correct
11 Correct 208 ms 41320 KB Output is correct
12 Correct 178 ms 40500 KB Output is correct
13 Correct 176 ms 47156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19924 KB Output is correct
2 Correct 17 ms 19924 KB Output is correct
3 Correct 16 ms 19916 KB Output is correct
4 Correct 15 ms 19924 KB Output is correct
5 Correct 17 ms 20044 KB Output is correct
6 Correct 22 ms 20308 KB Output is correct
7 Correct 22 ms 20292 KB Output is correct
8 Correct 22 ms 20300 KB Output is correct
9 Correct 28 ms 20456 KB Output is correct
10 Correct 26 ms 20428 KB Output is correct
11 Correct 26 ms 20540 KB Output is correct
12 Correct 19 ms 20404 KB Output is correct
13 Correct 26 ms 20436 KB Output is correct
14 Correct 24 ms 20416 KB Output is correct
15 Correct 28 ms 20676 KB Output is correct
16 Correct 27 ms 20444 KB Output is correct
17 Correct 29 ms 20532 KB Output is correct
18 Correct 25 ms 20180 KB Output is correct
19 Correct 23 ms 20412 KB Output is correct
20 Correct 21 ms 20180 KB Output is correct
21 Correct 20 ms 20212 KB Output is correct
22 Correct 16 ms 20052 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 53236 KB Output is correct
2 Correct 739 ms 53520 KB Output is correct
3 Correct 577 ms 53964 KB Output is correct
4 Correct 861 ms 54300 KB Output is correct
5 Correct 921 ms 50996 KB Output is correct
6 Correct 25 ms 20564 KB Output is correct
7 Correct 22 ms 20400 KB Output is correct
8 Correct 21 ms 20436 KB Output is correct
9 Correct 822 ms 47212 KB Output is correct
10 Correct 742 ms 46892 KB Output is correct
11 Correct 622 ms 46924 KB Output is correct
12 Correct 640 ms 46512 KB Output is correct
13 Execution timed out 3059 ms 59896 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 49028 KB Output is correct
2 Correct 184 ms 49080 KB Output is correct
3 Correct 196 ms 49108 KB Output is correct
4 Correct 223 ms 49040 KB Output is correct
5 Correct 166 ms 45120 KB Output is correct
6 Correct 18 ms 20532 KB Output is correct
7 Correct 18 ms 20300 KB Output is correct
8 Correct 19 ms 20356 KB Output is correct
9 Correct 234 ms 41464 KB Output is correct
10 Correct 225 ms 41284 KB Output is correct
11 Correct 208 ms 41320 KB Output is correct
12 Correct 178 ms 40500 KB Output is correct
13 Correct 176 ms 47156 KB Output is correct
14 Correct 17 ms 19924 KB Output is correct
15 Correct 17 ms 19924 KB Output is correct
16 Correct 16 ms 19916 KB Output is correct
17 Correct 15 ms 19924 KB Output is correct
18 Correct 17 ms 20044 KB Output is correct
19 Correct 22 ms 20308 KB Output is correct
20 Correct 22 ms 20292 KB Output is correct
21 Correct 22 ms 20300 KB Output is correct
22 Correct 28 ms 20456 KB Output is correct
23 Correct 26 ms 20428 KB Output is correct
24 Correct 26 ms 20540 KB Output is correct
25 Correct 19 ms 20404 KB Output is correct
26 Correct 26 ms 20436 KB Output is correct
27 Correct 24 ms 20416 KB Output is correct
28 Correct 28 ms 20676 KB Output is correct
29 Correct 27 ms 20444 KB Output is correct
30 Correct 29 ms 20532 KB Output is correct
31 Correct 25 ms 20180 KB Output is correct
32 Correct 23 ms 20412 KB Output is correct
33 Correct 21 ms 20180 KB Output is correct
34 Correct 20 ms 20212 KB Output is correct
35 Correct 16 ms 20052 KB Output is correct
36 Correct 705 ms 53236 KB Output is correct
37 Correct 739 ms 53520 KB Output is correct
38 Correct 577 ms 53964 KB Output is correct
39 Correct 861 ms 54300 KB Output is correct
40 Correct 921 ms 50996 KB Output is correct
41 Correct 25 ms 20564 KB Output is correct
42 Correct 22 ms 20400 KB Output is correct
43 Correct 21 ms 20436 KB Output is correct
44 Correct 822 ms 47212 KB Output is correct
45 Correct 742 ms 46892 KB Output is correct
46 Correct 622 ms 46924 KB Output is correct
47 Correct 640 ms 46512 KB Output is correct
48 Execution timed out 3059 ms 59896 KB Time limit exceeded
49 Halted 0 ms 0 KB -