oj.uz

Submission #635480

# Submission time Handle Problem Language Result Execution time Memory
635480 2022-08-26T10:17:48 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 242 ms 26000 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, NN=3e5+5, M=1e9+7;
int ans, q, n, r, st[N], fn[N], siz[N], num[N], ss[N];
int f[N+NN], rf[N+NN], cmo;
vector<int>g[N];

int tav(int a, int b){
    int res=1;
    while(b){
        if(b&1)
            res=1LL*res*a%M;
        a=1LL*a*a%M;
        b>>=1;
    }
    return res;
}

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

void pre(){
    f[0]=1;
    for(int i=1;i<N+NN;++i)
        f[i]=1LL*f[i-1]*i%M;
    rf[N+NN-1]=tav(f[N+NN-1], M-2);
    for(int i=N+NN-2;i>=0;--i)
        rf[i]=1LL*(i+1)*rf[i+1]%M;
}

struct seg_tree{
    int sz, h[3*N], lz[3*N], a[3*N], b[3*N];
    vector<int>ve;
    vector<pii>ev;

    seg_tree(){
        sz=1;
        while(sz<n)
            sz<<=1;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(lz, 0, sizeof(lz));
        fill(h, h+2*sz, 1);
    }

    int 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 adda(int x, int v){
        x=st[x];
        x+=sz-1;
        a[x]+=v;
        while(x){
            --x;
            x/=2;
            a[x]+=v;
        }
    }

    int 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 sumb(2*x+1, lx, m, l, r)+sumb(2*x+2, m, rx, l, r);
    }

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

    void add(int x, int lx, int rx, int l, int r, int t){
        if(lx>=r || rx<=l)
            return;
        if(lx>=l && rx<=r){
            h[x]+=t;
            lz[x]+=t;
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        add(2*x+1, lx, m, l, r, t);
        add(2*x+2, m, rx, l, r, t);
        h[x]=-max(-h[2*x+1], -h[2*x+2]);
    }

    void add(int l, int r, int t){
        add(0, 0, sz, l, r, t);
    }
    
    int min(int x, int lx, int rx, int i){
        if(lx==rx-1)
            return h[x];
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(i<m)
            return min(2*x+1, lx, m, i);
        return min(2*x+2, m, rx, i);    
    }

    void opr(int x, int lx, int rx, int r){
        if(lx>=r)
            return;
        if(rx<=r){
            ve.push_back(x);
            ev.push_back({lx, rx});
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        opr(2*x+2, m, rx, r);
        opr(2*x+1, lx, m, r);
    }

    int fr(int x, int lx, int rx, int val){
        if(lx+1==rx){
            if(h[x]>=val)
                return lx;
            return rx;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(h[2*x+2]>=val)
            return fr(2*x+1, lx, m, val);
        return fr(2*x+2, m, rx, val);
    }

    int par(int u){
        u=st[u];
        opr(0, 0, sz, u+1);
        int hh=min(0, 0, sz, u);
        int res=0;
        for(int i=0;i<ve.size();++i){
            if(ve[i]<hh){
                res=fr(ve[i], ev[i].F, ev[i].S, hh);
                break;
            }
        }
        ve.clear();
        ev.clear();
        return res;
    }
};

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){
            dfs(tm, u, v);
            ss[v]+=ss[u];
        }
    }
    fn[v]=tm;
}

void ud(const int &v){
    if(num[v]<0)
        --cmo;
    else
        ans=1LL*ans*tav(C(num[v]+siz[v]-1, siz[v]-1), M-2)%M;
}

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    cin>>n>>r;
    for(int i=0;i<n-1;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
    }
    int tm=0;
    dfs(tm, 0);
    seg_tree A;
    ans=C(r+n-1, n-1);
    cout<<ans<<'\n';
    siz[0]=n;
    num[0]=r;
    cin>>q;
    while(q--){
        int t, u;
        cin>>t>>u;
        --u;
        if(t==1){
            int v;
            cin>>v;
            int w=A.par(u);
            A.add(st[u], fn[u], 1);
            ud(w);
            siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
            A.adda(u, siz[u]);
            siz[w]-=siz[u];
            A.adda(w, -siz[u]);
            num[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
            A.addb(u, num[u]);
            num[w]-=num[u];
            A.addb(w, -num[u]);
            du(w);
            du(u);
        }
        else{
            A.add(st[u], fn[u], -1);
            int w=A.par(u);
            ud(w);
            ud(u);
            A.adda(u, -siz[u]);
            siz[w]+=siz[u];
            A.adda(w, siz[u]);
            A.addb(u, -num[u]);
            num[w]+=num[u];
            A.addb(w, num[u]);
            du(u);
        }
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
    }
}

Compilation message

Main.cpp: In member function 'int seg_tree::par(int)':
Main.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         for(int i=0;i<ve.size();++i){
      |                     ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 23448 KB Output is correct
2 Correct 67 ms 23412 KB Output is correct
3 Correct 67 ms 23424 KB Output is correct
4 Correct 66 ms 23376 KB Output is correct
5 Correct 90 ms 23764 KB Output is correct
6 Correct 16 ms 18424 KB Output is correct
7 Correct 15 ms 18468 KB Output is correct
8 Correct 15 ms 18336 KB Output is correct
9 Correct 66 ms 23808 KB Output is correct
10 Correct 64 ms 23756 KB Output is correct
11 Correct 78 ms 24264 KB Output is correct
12 Correct 82 ms 25300 KB Output is correct
13 Correct 57 ms 22988 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 23448 KB Output is correct
2 Correct 67 ms 23412 KB Output is correct
3 Correct 67 ms 23424 KB Output is correct
4 Correct 66 ms 23376 KB Output is correct
5 Correct 90 ms 23764 KB Output is correct
6 Correct 16 ms 18424 KB Output is correct
7 Correct 15 ms 18468 KB Output is correct
8 Correct 15 ms 18336 KB Output is correct
9 Correct 66 ms 23808 KB Output is correct
10 Correct 64 ms 23756 KB Output is correct
11 Correct 78 ms 24264 KB Output is correct
12 Correct 82 ms 25300 KB Output is correct
13 Correct 57 ms 22988 KB Output is correct
14 Incorrect 13 ms 18260 KB Output isn't correct
15 Halted 0 ms 0 KB -