oj.uz

Submission #468568

# Submission time Handle Problem Language Result Execution time Memory
468568 2021-08-28T19:02:10 Z alirezasamimi100 Sumtree (INOI20_sumtree) C++17
70 / 100
 3000 ms 83780 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=18,M=5e5+10,SQ=350,B=737,inf=1e9+10;
const ll INF=1e18;
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,g[N*4],st[N],fn[N],t,p[N][LN],lz[N*4],F[M],I[M],R,q,ans,z;
pll f[N*4];
vector<ll> adj[N];
pll operator+(pll a, pll b){
    if(a.F<b.F) return a;
    if(b.F<a.F) return b;
    return mp(a.F,a.S+b.S);
}
void dfs(ll v, ll P){
    p[v][0]=P;
    for(ll i=1; i<LN; i++) p[v][i]=p[p[v][i-1]][i-1];
    st[v]=++t;
    for(ll u : adj[v]) if(u!=P) dfs(u,v);
    fn[v]=t;
}
void update(ll v, ll l, ll r, ll p, ll x){
    if(r-l==1){
        g[v]+=x;
        return;
    }
    ll m=(l+r)>>1;
    if(p<m) update(lc,l,m,p,x);
    else update(rc,m,r,p,x);
    g[v]=g[lc]+g[rc];
}
ll get(ll v, ll l, ll r, ll tl, ll tr){
    if(l>=tr || tl>=r) return 0;
    if(l>=tl && r<=tr) return g[v];
    ll m=(l+r)>>1;
    return get(lc,l,m,tl,tr)+get(rc,m,r,tl,tr);
}
void build(ll v, ll l, ll r){
    f[v].S=r-l;
    if(r-l>1){
        ll m=(l+r)>>1;
        build(lc,l,m);
        build(rc,m,r);
    }
}
void shift(ll v, ll l, ll r){
    f[v].F+=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}
void upd(ll v, ll l, ll r, ll tl, ll tr, ll x){
    shift(v,l,r);
    if(l>=tr || tl>=r) return;
    if(l>=tl && r<=tr){
        lz[v]+=x;
        return shift(v,l,r);
    }
    ll m=(l+r)>>1;
    upd(lc,l,m,tl,tr,x);
    upd(rc,m,r,tl,tr,x);
    f[v]=f[lc]+f[rc];
}
pll gt(ll v, ll l, ll r, ll tl, ll tr){
    shift(v,l,r);
    if(l>=tr || tl>=r) return mp(INF,0ll);
    if(l>=tl && r<=tr) return f[v];
    ll m=(l+r)>>1;
    return gt(lc,l,m,tl,tr)+gt(rc,m,r,tl,tr);
}
ll C(ll x, ll y){
    if(y>x) return 0;
    return F[x]*I[y]%MOD*I[x-y]%MOD;
}
ll fp(ll v){
    ll x=gt(1,1,n+1,st[v],st[v]+1).F;
    for(ll i=LN; i--;){
        ll k=p[v][i];
        if(k && gt(1,1,n+1,st[k],st[k]+1).F==x) v=k;
    }
    return v;
}
ll calc(ll v){
    ll x=get(1,1,n+1,st[v],st[v]+1),y=gt(1,1,n+1,st[v],fn[v]+1).S;
    return C(x+y-1,y-1);
}
int main(){
    fast_io;
    cin >> n >> R;
    F[0]=I[0]=1;
    for(ll i=1; i<M; i++){
        F[i]=F[i-1]*i%MOD;
        I[i]=pow(F[i],MOD-2,MOD);
    }
    for(ll i=1; i<n; i++){
        ll v,u;
        cin >> v >> u;
        adj[v].pb(u);
        adj[u].pb(v);
    }
    dfs(1,0);
    build(1,1,n+1);
    upd(1,1,n+1,1,n+1,1);
    update(1,1,n+1,1,R);
    ans=calc(1);
    cout << ans << '\n';
    cin >> q;
    while(q--){
        ll k,v,x,u,y;
        cin >> k >> v;
        if(k==1){
            cin >> x;
            u=fp(v);
            y=calc(u);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            x-=get(1,1,n+1,st[v],fn[v]+1);
            update(1,1,n+1,st[v],x);
            update(1,1,n+1,st[u],-x);
            upd(1,1,n+1,st[v],fn[v]+1,1);
            y=calc(u);
            if(y) ans=ans*y%MOD;
            else z++;
            y=calc(v);
            if(y) ans=ans*y%MOD;
            else z++;
        }else{
            u=fp(p[v][0]);
            y=calc(u);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            y=calc(v);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            upd(1,1,n+1,st[v],fn[v]+1,-1);
            x=get(1,1,n+1,st[v],st[v]+1);
            update(1,1,n+1,st[v],-x);
            update(1,1,n+1,st[u],x);
            y=calc(u);
            if(y) ans=ans*y%MOD;
            else z++;
        }
        if(z) cout << 0 << '\n';
        else cout << ans << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 64452 KB Output is correct
2 Correct 262 ms 64420 KB Output is correct
3 Correct 258 ms 64324 KB Output is correct
4 Correct 288 ms 64324 KB Output is correct
5 Correct 219 ms 60964 KB Output is correct
6 Correct 84 ms 13624 KB Output is correct
7 Correct 83 ms 13564 KB Output is correct
8 Correct 83 ms 13584 KB Output is correct
9 Correct 265 ms 59872 KB Output is correct
10 Correct 248 ms 59672 KB Output is correct
11 Correct 253 ms 59796 KB Output is correct
12 Correct 241 ms 57924 KB Output is correct
13 Correct 236 ms 60456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 12872 KB Output is correct
2 Correct 84 ms 12840 KB Output is correct
3 Correct 84 ms 12868 KB Output is correct
4 Correct 84 ms 12860 KB Output is correct
5 Correct 85 ms 12928 KB Output is correct
6 Correct 91 ms 13404 KB Output is correct
7 Correct 91 ms 13512 KB Output is correct
8 Correct 91 ms 13368 KB Output is correct
9 Correct 97 ms 13720 KB Output is correct
10 Correct 98 ms 13700 KB Output is correct
11 Correct 98 ms 13684 KB Output is correct
12 Correct 86 ms 13676 KB Output is correct
13 Correct 98 ms 13668 KB Output is correct
14 Correct 97 ms 13640 KB Output is correct
15 Correct 97 ms 13812 KB Output is correct
16 Correct 92 ms 13736 KB Output is correct
17 Correct 98 ms 13692 KB Output is correct
18 Correct 94 ms 13128 KB Output is correct
19 Correct 93 ms 13636 KB Output is correct
20 Correct 89 ms 13328 KB Output is correct
21 Correct 90 ms 13280 KB Output is correct
22 Correct 83 ms 12900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 72232 KB Output is correct
2 Correct 563 ms 72452 KB Output is correct
3 Correct 366 ms 72644 KB Output is correct
4 Correct 857 ms 73092 KB Output is correct
5 Correct 1557 ms 70252 KB Output is correct
6 Correct 90 ms 13844 KB Output is correct
7 Correct 85 ms 13644 KB Output is correct
8 Correct 90 ms 13732 KB Output is correct
9 Correct 1083 ms 69148 KB Output is correct
10 Correct 887 ms 68676 KB Output is correct
11 Correct 797 ms 68676 KB Output is correct
12 Correct 810 ms 68232 KB Output is correct
13 Correct 1283 ms 78260 KB Output is correct
14 Correct 1280 ms 83780 KB Output is correct
15 Correct 1281 ms 83660 KB Output is correct
16 Correct 1277 ms 83652 KB Output is correct
17 Correct 1300 ms 83652 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 69956 KB Output is correct
2 Correct 1403 ms 70184 KB Output is correct
3 Correct 1278 ms 70232 KB Output is correct
4 Correct 1499 ms 70136 KB Output is correct
5 Correct 1428 ms 68148 KB Output is correct
6 Correct 1300 ms 69944 KB Output is correct
7 Correct 1139 ms 42452 KB Output is correct
8 Correct 1411 ms 42376 KB Output is correct
9 Correct 1565 ms 70232 KB Output is correct
10 Correct 1225 ms 70080 KB Output is correct
11 Correct 1208 ms 70152 KB Output is correct
12 Correct 1062 ms 42508 KB Output is correct
13 Correct 825 ms 37732 KB Output is correct
14 Correct 1026 ms 40160 KB Output is correct
15 Correct 1283 ms 41048 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 64452 KB Output is correct
2 Correct 262 ms 64420 KB Output is correct
3 Correct 258 ms 64324 KB Output is correct
4 Correct 288 ms 64324 KB Output is correct
5 Correct 219 ms 60964 KB Output is correct
6 Correct 84 ms 13624 KB Output is correct
7 Correct 83 ms 13564 KB Output is correct
8 Correct 83 ms 13584 KB Output is correct
9 Correct 265 ms 59872 KB Output is correct
10 Correct 248 ms 59672 KB Output is correct
11 Correct 253 ms 59796 KB Output is correct
12 Correct 241 ms 57924 KB Output is correct
13 Correct 236 ms 60456 KB Output is correct
14 Correct 82 ms 12872 KB Output is correct
15 Correct 84 ms 12840 KB Output is correct
16 Correct 84 ms 12868 KB Output is correct
17 Correct 84 ms 12860 KB Output is correct
18 Correct 85 ms 12928 KB Output is correct
19 Correct 91 ms 13404 KB Output is correct
20 Correct 91 ms 13512 KB Output is correct
21 Correct 91 ms 13368 KB Output is correct
22 Correct 97 ms 13720 KB Output is correct
23 Correct 98 ms 13700 KB Output is correct
24 Correct 98 ms 13684 KB Output is correct
25 Correct 86 ms 13676 KB Output is correct
26 Correct 98 ms 13668 KB Output is correct
27 Correct 97 ms 13640 KB Output is correct
28 Correct 97 ms 13812 KB Output is correct
29 Correct 92 ms 13736 KB Output is correct
30 Correct 98 ms 13692 KB Output is correct
31 Correct 94 ms 13128 KB Output is correct
32 Correct 93 ms 13636 KB Output is correct
33 Correct 89 ms 13328 KB Output is correct
34 Correct 90 ms 13280 KB Output is correct
35 Correct 83 ms 12900 KB Output is correct
36 Correct 366 ms 72232 KB Output is correct
37 Correct 563 ms 72452 KB Output is correct
38 Correct 366 ms 72644 KB Output is correct
39 Correct 857 ms 73092 KB Output is correct
40 Correct 1557 ms 70252 KB Output is correct
41 Correct 90 ms 13844 KB Output is correct
42 Correct 85 ms 13644 KB Output is correct
43 Correct 90 ms 13732 KB Output is correct
44 Correct 1083 ms 69148 KB Output is correct
45 Correct 887 ms 68676 KB Output is correct
46 Correct 797 ms 68676 KB Output is correct
47 Correct 810 ms 68232 KB Output is correct
48 Correct 1283 ms 78260 KB Output is correct
49 Correct 1280 ms 83780 KB Output is correct
50 Correct 1281 ms 83660 KB Output is correct
51 Correct 1277 ms 83652 KB Output is correct
52 Correct 1300 ms 83652 KB Output is correct
53 Correct 1474 ms 69956 KB Output is correct
54 Correct 1403 ms 70184 KB Output is correct
55 Correct 1278 ms 70232 KB Output is correct
56 Correct 1499 ms 70136 KB Output is correct
57 Correct 1428 ms 68148 KB Output is correct
58 Correct 1300 ms 69944 KB Output is correct
59 Correct 1139 ms 42452 KB Output is correct
60 Correct 1411 ms 42376 KB Output is correct
61 Correct 1565 ms 70232 KB Output is correct
62 Correct 1225 ms 70080 KB Output is correct
63 Correct 1208 ms 70152 KB Output is correct
64 Correct 1062 ms 42508 KB Output is correct
65 Correct 825 ms 37732 KB Output is correct
66 Correct 1026 ms 40160 KB Output is correct
67 Correct 1283 ms 41048 KB Output is correct
68 Correct 83 ms 12872 KB Output is correct
69 Correct 83 ms 12868 KB Output is correct
70 Correct 2381 ms 79424 KB Output is correct
71 Correct 2655 ms 79196 KB Output is correct
72 Correct 2740 ms 79428 KB Output is correct
73 Correct 2794 ms 79256 KB Output is correct
74 Execution timed out 3021 ms 79060 KB Time limit exceeded
75 Halted 0 ms 0 KB -