oj.uz

Submission #468564

# Submission time Handle Problem Language Result Execution time Memory
468564 2021-08-28T18:50:04 Z alirezasamimi100 Sumtree (INOI20_sumtree) C++17
10 / 100
 1041 ms 144320 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=17,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){
    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 266 ms 65344 KB Output is correct
2 Correct 274 ms 65276 KB Output is correct
3 Correct 278 ms 65304 KB Output is correct
4 Correct 265 ms 65220 KB Output is correct
5 Correct 232 ms 61892 KB Output is correct
6 Correct 84 ms 13648 KB Output is correct
7 Correct 87 ms 13508 KB Output is correct
8 Correct 84 ms 13604 KB Output is correct
9 Correct 292 ms 60792 KB Output is correct
10 Correct 265 ms 60496 KB Output is correct
11 Correct 262 ms 60692 KB Output is correct
12 Correct 257 ms 58736 KB Output is correct
13 Correct 246 ms 61220 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1041 ms 138808 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 266 ms 65344 KB Output is correct
2 Correct 274 ms 65276 KB Output is correct
3 Correct 278 ms 65304 KB Output is correct
4 Correct 265 ms 65220 KB Output is correct
5 Correct 232 ms 61892 KB Output is correct
6 Correct 84 ms 13648 KB Output is correct
7 Correct 87 ms 13508 KB Output is correct
8 Correct 84 ms 13604 KB Output is correct
9 Correct 292 ms 60792 KB Output is correct
10 Correct 265 ms 60496 KB Output is correct
11 Correct 262 ms 60692 KB Output is correct
12 Correct 257 ms 58736 KB Output is correct
13 Correct 246 ms 61220 KB Output is correct
14 Incorrect 83 ms 12868 KB Output isn't correct
15 Halted 0 ms 0 KB -