oj.uz

Submission #635504

# Submission time Handle Problem Language Result Execution time Memory
635504 2022-08-26T10:49:43 Z K4YAN Sumtree (INOI20_sumtree) C++17
30 / 100
 1708 ms 284288 KB 
//Be Name Khoda

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ll mxn = 2e5 + 16, MX = 3e5 + 16, md = 1e9 + 7;
ll n, r, t, q, w, cnt, pw;
ll st[mxn], ft[mxn], dp[mxn], h[mxn], subt[mxn], R[mxn], fact[MX + mxn], taq[MX + mxn], par[mxn][19];
vector<ll> adj[mxn];
bitset<mxn> mark;
set<int> s[2 * MX];

inline ll tav(ll a, ll b) {
    ll res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % md;
        a = a * a % md, b >>= 1;
    } return res;
}

inline ll chs(ll a, ll b) {
    if(a < 0 || b > a) return 0;
    return fact[a] * taq[b] % md * taq[a - b] % md;
}

inline void fun() {
    fact[0] = 1;
    for(int i = 1; i < MX + mxn; i++) {
        fact[i] = fact[i - 1] * i % md;
    } taq[MX + mxn - 1] = tav(fact[MX + mxn - 1], md - 2);
    for(int i = MX + mxn - 2; i > -1; i--) {
        taq[i] = taq[i + 1] * (i + 1) % md;
    } return;
}

void DFS(int v) {
    mark.set(v);
    st[v] = q++, subt[v] = 1;
    for(int i = 1; i < 19; i++) {
        par[v][i] = par[par[v][i - 1]][i - 1];
    } for(auto u : adj[v]) {
        if(!mark[u]) {
            par[u][0] = v;
            h[u] = h[v] + 1;
            DFS(u);
            subt[v] += subt[u];
        }
    } ft[v] = q;
    return;
}

inline int find_par(int v, int x) {
    for(int i = 18; i > -1; i--) {
        if(x & (1 << i)) {
            v = par[v][i];
            x -= (1 << i);
            if(x == 0) return v;
        }
    } return v;
}

struct segtree {

    int sz = 1;
    vector<pll> v;

    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, {0, 0});
        return;
    }
    void set(int i, pll p, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] = p;
            return;
        } int m = (lx + rx) >> 1;
        if(i < m) {
            set(i, p, 2 * x + 1, lx, m);
        } else {
            set(i, p, 2 * x + 2, m, rx);
        } v[x].first = v[2 * x + 1].first + v[2 * x + 2].first;
        v[x].second = v[2 * x + 1].second + v[2 * x + 2].second;
        return;
    }
    void set(int i, pll p) {
        set(i, p, 0, 0, sz);
        return;
    }
    pll ask(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {0, 0};
        if(l <= lx && rx <= r) {
            return v[x];
        } int m = (lx + rx) >> 1;
        pll a = ask(l, r, 2 * x + 1, lx, m);
        pll b = ask(l, r, 2 * x + 2, m, rx);
        return {a.first + b.first, a.second + b.second};
    }
    pll ask(int l, int r) {
        return ask(l, r, 0, 0, sz);
    }

}; segtree stt;

struct fp {

    int sz = 1;
    
    void init(ll n) {
        while(sz < n) sz <<= 1;
        return;
    }
    void add(int l, int r, int q, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            s[x].insert(-q);
            return;
        } int m = (lx + rx) >> 1;
        add(l, r, q, 2 * x + 1, lx, m);
        add(l, r, q, 2 * x + 2, m, rx);
        return;
    }
    void add(int l, int r, int q) {
        add(l, r, q, 0, 0, sz);
        return;
    }
    int ask(int i, int x, int lx, int rx) {
        int a = 0;
        if(int(s[x].size()) > 0) {
            a = *(s[x].begin()), a = -a;
        }
        if(rx - lx == 1) {
            if(int(s[x].size()) == 0) return 0;
            return -1 * (*(s[x].begin()));
        } int m = (lx + rx) >> 1;
        if(i < m) {
            return max(a, ask(i, 2 * x + 1, lx, m));
        } else {
            return max(a, ask(i, 2 * x + 2, m, rx));
        }
    }
    int ask(int i) {
        return ask(i, 0, 0, sz);
    }
    void rem(int l, int r, int q, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            s[x].erase(-q);
            return;
        } int m = (lx + rx) >> 1;
        rem(l, r, q, 2 * x + 1, lx, m);
        rem(l, r, q, 2 * x + 2, m, rx);
        return;
    }
    void rem(int l, int r, int q) {
        rem(l, r, q, 0, 0, sz);
        return;
    }

}; fp fpar;

inline void input() {

    cin >> n >> r;
    for(int i = 1; i < n; i++) {
        cin >> q >> w;
        adj[q].push_back(w);
        adj[w].push_back(q);
    } cin >> t;

}

inline void solve() {

    fun(); q = 0;
    DFS(1);
    fill(dp, dp + mxn, 1);
    dp[1] = pw = chs(r + n - 1, n - 1);
    cout << pw << "\n";
    stt.init(n), fpar.init(n);
    fpar.add(1, n, 0); R[1] = r;
    for(int tt = 0; tt < t; tt++) {
        cin >> q;
        if(q == 1) {
            cin >> q >> w;
            R[q] = w;
            ll v = fpar.ask(st[q]), x, rp, sp;
            pll p;
            v = find_par(q, h[q] - v);
            if(dp[v] == 0) cnt--;
            else pw = pw * tav(dp[v], md - 2) % md;
            p = stt.ask(st[q] + 1, ft[q]);
            rp = R[q] - p.first, sp = subt[q] - p.second;
            x = chs(rp + sp - 1, sp - 1);
            if(x == 0) cnt++, dp[q] = 0;
            else {
                dp[q] = x, pw = pw * x % md;
            } stt.set(st[q], {rp, sp});
            fpar.add(st[q] + 1, ft[q], h[q]);
            p = stt.ask(st[v] + 1, ft[v]);
            rp = R[v] - p.first, sp = subt[v] - p.second;
            x = chs(rp + sp - 1, sp - 1);
            if(x == 0) cnt++, dp[v] = 0;
            else {
                dp[v] = x, pw = pw * x % md;
            } stt.set(st[v], {rp, sp});
            if(cnt == 0) {
                cout << pw << "\n";
            } else {
                cout << "0\n";
            }
            continue;
        } cin >> q;
        ll v = fpar.ask(st[q]), x, rp, sp;
        pll p;
        v = find_par(q, h[q] - v);
        if(dp[q] == 0) {
            cnt--, dp[q] = 1;
        } else {
            pw = pw * tav(dp[q], md - 2) % md, dp[q] = 1;
        } R[q] = 0;
        stt.set(st[q], {0, 0});
        fpar.rem(st[q] + 1, ft[q], h[q]);
        if(dp[v] == 0) {
            cnt--;
        } else {
            pw = pw * tav(dp[v], md - 2) % md;
        } 
        p = stt.ask(st[v] + 1, ft[v]);
        rp = R[v] - p.first, sp = subt[v] - p.second;
        x = chs(rp + sp - 1, sp - 1);
        if(x == 0) {
            cnt++, dp[x] = 0;
        } else {
            dp[x] = x, pw = pw * x % md;
        } stt.set(st[v], {rp, sp});
        if(cnt == 0) {
            cout << pw << "\n";
        } else {
            cout << "0\n";
        }
    }
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 101912 KB Output is correct
2 Correct 212 ms 101940 KB Output is correct
3 Correct 195 ms 101904 KB Output is correct
4 Correct 190 ms 101968 KB Output is correct
5 Correct 173 ms 96944 KB Output is correct
6 Correct 29 ms 43636 KB Output is correct
7 Correct 31 ms 43324 KB Output is correct
8 Correct 30 ms 43452 KB Output is correct
9 Correct 216 ms 94272 KB Output is correct
10 Correct 209 ms 94048 KB Output is correct
11 Correct 219 ms 94284 KB Output is correct
12 Correct 227 ms 92108 KB Output is correct
13 Correct 181 ms 97612 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 105316 KB Output is correct
2 Correct 319 ms 113212 KB Output is correct
3 Correct 234 ms 108784 KB Output is correct
4 Correct 453 ms 122576 KB Output is correct
5 Correct 945 ms 162928 KB Output is correct
6 Correct 33 ms 44220 KB Output is correct
7 Correct 31 ms 43456 KB Output is correct
8 Correct 36 ms 43700 KB Output is correct
9 Correct 504 ms 105816 KB Output is correct
10 Correct 463 ms 103940 KB Output is correct
11 Correct 409 ms 103424 KB Output is correct
12 Correct 465 ms 104336 KB Output is correct
13 Correct 1226 ms 237396 KB Output is correct
14 Correct 1708 ms 284288 KB Output is correct
15 Correct 1580 ms 274856 KB Output is correct
16 Correct 1642 ms 274876 KB Output is correct
17 Correct 1567 ms 274928 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 101912 KB Output is correct
2 Correct 212 ms 101940 KB Output is correct
3 Correct 195 ms 101904 KB Output is correct
4 Correct 190 ms 101968 KB Output is correct
5 Correct 173 ms 96944 KB Output is correct
6 Correct 29 ms 43636 KB Output is correct
7 Correct 31 ms 43324 KB Output is correct
8 Correct 30 ms 43452 KB Output is correct
9 Correct 216 ms 94272 KB Output is correct
10 Correct 209 ms 94048 KB Output is correct
11 Correct 219 ms 94284 KB Output is correct
12 Correct 227 ms 92108 KB Output is correct
13 Correct 181 ms 97612 KB Output is correct
14 Incorrect 24 ms 42572 KB Output isn't correct
15 Halted 0 ms 0 KB -