oj.uz

Submission #636142

# Submission time Handle Problem Language Result Execution time Memory
636142 2022-08-28T09:38:44 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 50888 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5, M=1e9+7;
int n, r, q, f[5*N/2], rf[5*N/2], ans, cmo, siz[N];
int ss[N], pr[N][18], st[N], fn[N];
vector<int>g[N];
ll tp[N];

inline int tav(int x, int y){
    ll res=1;
    while(y){
        if(y&1)
            res=res*x%M;
        y>>=1;
        x=1LL*x*x%M;
    }
    return res;
}

inline int rev(const int &x){
    return tav(x, M-2); 
}

void pre(){
    f[0]=1;
    int t=5*N/2;
    for(int i=1;i<t;++i)
        f[i]=1LL*f[i-1]*i%M;
    rf[t-1]=rev(f[t-1]);
    for(int i=t-2;i>=0;--i)
        rf[i]=1LL*rf[i+1]*(i+1)%M;
}

int C(int x, int y){
    ll res=1LL*f[x]*rf[y]%M;
    return res*rf[x-y]%M;
}

void dfs(int &tm, const int &v, const int &p=-1){
    st[v]=tm++;
    ss[v]=1;
    for(int u: g[v]){
        if(u!=p){
            pr[u][0]=v;
            for(int i=1;i<18;++i)
                pr[u][i]=pr[pr[u][i-1]][i-1];
            dfs(tm, u, v);
            ss[v]+=ss[u];
        }
    }
    fn[v]=tm;
}

void dfs(){
    int tm=0;
    dfs(tm, 0);
}

struct seg_tree{
    int sz, h[3*N];
    ll a[3*N], b[3*N];
    
    void add(int x, int lx, int rx, int l, int r, int val){
        if(lx>=r || rx<=l)
            return;
        if(lx>=l && rx<=r){
            h[x]+=val;
            return;
        }
        int m=(lx+rx)/2;
        add(2*x+1, lx, m, l, r, val);
        add(2*x+2, m, rx, l, r, val);
    }

    int num(int x){
        x+=sz-1;
        int res=h[x];
        while(x){
            --x;
            x/=2;
            res+=h[x];
        }
        return res;
    }

    void adda(int x, int val){
        x+=sz-1;
        a[x]+=val;
        while(x){
            --x;
            x/=2;
            a[x]+=val;
        }
    }

    ll suma(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return a[x];
        int m=(lx+rx)/2;
        return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
    }

    void addb(int x, int val){
        x+=sz-1;
        b[x]+=val;
        while(x){
            --x;
            x/=2;
            b[x]+=val;
        }
    }

    ll sumb(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return b[x];
        int m=(lx+rx)/2;
        return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
    }
    
    void upd(){
        sz=1;
        while(sz<n)
            sz<<=1;
        add(0, 0, sz, 0, n, 1);
        adda(0, n);
        addb(0, r);
    }
} A;

int par(int v){
    int h=A.num(st[v]);
    for(int i=17;i>=0;--i){
        int u=pr[v][i];
        if(A.num(st[u])==h)
            v=u;
    }
    return v;
}

inline void du(const int &u){
    if(tp[u]<0)
        ++cmo;
    else
        ans=1LL*ans*C(siz[u]+tp[u]-1, siz[u]-1)%M;
}

inline void ud(const int &u){
    if(tp[u]<0)
        --cmo;
    else
        ans=1LL*ans*rev(C(siz[u]+tp[u]-1, siz[u]-1))%M;
}

void add_u(int u, int v){
    int w=par(u);
    A.add(0, 0, A.sz, st[u], fn[u], 1);
    ud(w);
    siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
    tp[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
    du(u);
    A.adda(st[u], siz[u]);
    A.addb(st[u], tp[u]);
    siz[w]-=siz[u];
    tp[w]-=tp[u];
    du(w);
    A.adda(st[w], -siz[u]);
    A.addb(st[w], -tp[u]);
}

void erase_u(int u){
    A.add(0, 0, A.sz, st[u], fn[u], -1);
    int w=par(u);
    ud(u);
    ud(w);
    siz[w]+=siz[u];
    tp[w]+=tp[u];
    du(w);
    A.adda(st[u], -siz[u]);
    A.addb(st[u], -tp[u]);
    A.adda(st[w], siz[u]);
    A.addb(st[w], tp[u]);
    siz[u]=tp[u]=0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    cin>>n>>r;
    for(int i=1;i<n;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    dfs();
    A.upd();
    siz[0]=n;
    tp[0]=r;
    ans=C(r+n-1, n-1);
    cout<<ans<<'\n';
    cin>>q;
    while(q--){
        for(int i=0;i<n;++i){
            if(siz[i]<0 || siz[i]>ss[i]){
                cout<<1/0;
            }
        }
        int t, u;
        cin>>t>>u;
        --u;
        if(t==1){
            int v;
            cin>>v;
            add_u(u, v);
        }
        else
            erase_u(u);
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
    }
}
/*
9 10
1 2
1 3
3 4
3 9
9 6
9 8
5 6
7 6
5
1 3 11
1 6 7
2 3
1 7 7
2 6
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:215:24: warning: division by zero [-Wdiv-by-zero]
  215 |                 cout<<1/0;
      |                       ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 41420 KB Output is correct
2 Correct 159 ms 41416 KB Output is correct
3 Correct 145 ms 41360 KB Output is correct
4 Correct 148 ms 41500 KB Output is correct
5 Correct 119 ms 36748 KB Output is correct
6 Correct 12 ms 9556 KB Output is correct
7 Correct 12 ms 9300 KB Output is correct
8 Correct 12 ms 9364 KB Output is correct
9 Correct 174 ms 32260 KB Output is correct
10 Correct 150 ms 32260 KB Output is correct
11 Correct 173 ms 32192 KB Output is correct
12 Correct 165 ms 31224 KB Output is correct
13 Correct 124 ms 39116 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 41420 KB Output is correct
2 Correct 159 ms 41416 KB Output is correct
3 Correct 145 ms 41360 KB Output is correct
4 Correct 148 ms 41500 KB Output is correct
5 Correct 119 ms 36748 KB Output is correct
6 Correct 12 ms 9556 KB Output is correct
7 Correct 12 ms 9300 KB Output is correct
8 Correct 12 ms 9364 KB Output is correct
9 Correct 174 ms 32260 KB Output is correct
10 Correct 150 ms 32260 KB Output is correct
11 Correct 173 ms 32192 KB Output is correct
12 Correct 165 ms 31224 KB Output is correct
13 Correct 124 ms 39116 KB Output is correct
14 Incorrect 10 ms 8948 KB Output isn't correct
15 Halted 0 ms 0 KB -