oj.uz

Submission #635498

# Submission time Handle Problem Language Result Execution time Memory
635498 2022-08-26T10:42:42 Z MohammadAghil Sumtree (INOI20_sumtree) C++17
10 / 100
 502 ms 106060 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 21, inf = ll(1e9) + 5;

struct SegMul{
    vector<ll> seg;
    int n;
    SegMul(int n): n(n){
        seg.assign(n<<1, 1);
    }
    void upd(int i, ll k){
        for(i += n, seg[i] = k; i > 1; i >>= 1) seg[i>>1] = seg[i]*seg[i^1]%mod;
    }
    int get(){
        return seg[1];
    }
};

struct Fen{
    vector<int> fen;
    Fen(int n){
        fen.assign(n + 1, 0);
    }
    void upd(int i, int k){
        for(i++; i < sz(fen); i += i&-i) fen[i] += k;
    }
    int get(int i){
        int res = 0;
        for(i++; i; i -= i&-i) res += fen[i];
        return res;
    }
    int get(int l, int r){
        return get(r - 1) - get(l - 1);
    }
};


ll pw(ll a, ll b){
    if(!b) return 1;
    ll k = pw(a, b>>1ll);
    return  k*k%mod*(b&1ll?a:1ll)%mod;
}

ll fac[maxn], inv[maxn];

ll C(int n, int r){
    if(r < 0 || r > n) return 0;
    return fac[n]*inv[r]%mod*inv[n-r]%mod;
}


vector<int> adj[maxn];
int st[maxn], en[maxn], h[maxn], par[maxn][lg], t, cnt[maxn], val[maxn];

void dfs(int r, int p){
    cnt[r] = 1;
    st[r] = t++;
    par[r][0] = p;
    rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
    for(int c: adj[r]) if(c - p){
        h[c] = h[r] + 1;
        dfs(c, r);
        cnt[r] += cnt[c];
    }
    en[r] = t;
}

int main(){ IOS();
    fac[0] = inv[0] = 1;

    rep(i,1,maxn){
        fac[i] = fac[i-1]*i%mod;
        inv[i] = pw(fac[i], mod-2);
    }

    int n, r; cin >> n >> r;
    val[0] = r;

    rep(i,1,n){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb(v), adj[v].pb(u);
    }
    dfs(0, 0);
    int q; cin >> q;

    SegMul smul(n); smul.upd(0, C(r + n - 1, r));
    Fen fen_par(n); fen_par.upd(st[0], 1), fen_par.upd(en[0], -1);
    Fen cnt_sub(n); cnt_sub.upd(0, n);
    Fen sum_val(n); sum_val.upd(0, r);

    auto get_par = [&](int r){
        int vl = fen_par.get(st[r]);
        per(i,lg-1,0){
            int p = par[r][i];
            if(vl == fen_par.get(st[p])) r = p;
        }
        return par[r][0];
    };

    auto add = [&](int r, int x){
        int p = get_par(r);
        fen_par.upd(st[r], 1), fen_par.upd(en[r], -1);
        int fl = cnt_sub.get(st[r], en[r]);
        int emp = cnt[r] - fl;
        cnt_sub.upd(st[r], emp);
        cnt_sub.upd(st[p], -emp);
        sum_val.upd(st[r], val[r] = x - sum_val.get(st[r], en[r]));
        smul.upd(r, C(val[r] + emp - 1, val[r]));
        sum_val.upd(st[p], -val[r]); val[p] -= val[r];
        emp = cnt_sub.get(st[p], st[p] + 1);
        smul.upd(p, C(val[p] + emp - 1, val[p]));
    };

    auto rem = [&](int r){
        fen_par.upd(st[r], -1), fen_par.upd(en[r], 1);
        int p = get_par(r);
//        er(r, p);
        int tmp;
        cnt_sub.upd(st[r], tmp = -cnt_sub.get(st[r], st[r] + 1));
        cnt_sub.upd(st[p], -tmp);
        sum_val.upd(st[r], -val[r]);
        smul.upd(r, 1);
        sum_val.upd(st[p], val[r]); val[p] += val[r], val[r] = 0;
        int emp = cnt_sub.get(st[p], st[p] + 1);
//        er(emp, val[p], C(val[p] + emp - 1, emp));
        smul.upd(p, C(val[p] + emp - 1, val[p]));
    };

    cout << smul.get() << '\n';
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int u, x; cin >> u >> x; u--;
            add(u, x);
        }else{
            int u; cin >> u; u--;
            rem(u);
        }
        cout << smul.get() << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 59152 KB Output is correct
2 Correct 285 ms 59124 KB Output is correct
3 Correct 270 ms 59032 KB Output is correct
4 Correct 248 ms 59040 KB Output is correct
5 Correct 232 ms 55188 KB Output is correct
6 Correct 113 ms 20664 KB Output is correct
7 Correct 107 ms 20356 KB Output is correct
8 Correct 106 ms 20360 KB Output is correct
9 Correct 258 ms 51496 KB Output is correct
10 Correct 267 ms 51276 KB Output is correct
11 Correct 268 ms 51364 KB Output is correct
12 Correct 260 ms 49804 KB Output is correct
13 Correct 238 ms 55988 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 502 ms 106060 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 253 ms 59152 KB Output is correct
2 Correct 285 ms 59124 KB Output is correct
3 Correct 270 ms 59032 KB Output is correct
4 Correct 248 ms 59040 KB Output is correct
5 Correct 232 ms 55188 KB Output is correct
6 Correct 113 ms 20664 KB Output is correct
7 Correct 107 ms 20356 KB Output is correct
8 Correct 106 ms 20360 KB Output is correct
9 Correct 258 ms 51496 KB Output is correct
10 Correct 267 ms 51276 KB Output is correct
11 Correct 268 ms 51364 KB Output is correct
12 Correct 260 ms 49804 KB Output is correct
13 Correct 238 ms 55988 KB Output is correct
14 Incorrect 108 ms 19932 KB Output isn't correct
15 Halted 0 ms 0 KB -