oj.uz

Submission #780633

# Submission time Handle Problem Language Result Execution time Memory
780633 2023-07-12T11:05:31 Z Sami_Massah Sumtree (INOI20_sumtree) C++17
50 / 100
 3000 ms 66104 KB 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 5e5 + 12, lg = 20, mod = 1e9 + 7;
int n, bs, tz, tms, col[maxn], par[maxn][lg], sz[maxn], st[maxn], en[maxn], L[maxn * 4], R[maxn * 4], sum1[maxn * 4], sum2[maxn * 4];
long long ans, fact[maxn], rfact[maxn];
vector <int> conn[maxn];
vector <pair<int, int>> locs;
bitset <maxn> marked, zero;
long long tav(long long a, long long b){
    if(b == 0)
        return 1;
    a %= mod;
    long long x = tav(a * a % mod, b / 2);
    if(b % 2)
        return x * a % mod;
    return x % mod;
}
void make_tree(int l, int r, int ind){
    int mid = (l + r) / 2;
    L[ind] = l;
    R[ind] = r;
    if(l == r)
        return;
    make_tree(l, mid, ind * 2);
    make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree1(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        sum1[u] = k;
        return;
    }
    update_tree1(l, r, u * 2, k);
    update_tree1(l, r, u * 2 + 1, k);
    sum1[u] = sum1[u * 2] + sum1[u * 2 + 1];
}
void update_tree2(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        sum2[u] = k;
        return;
    }
    update_tree2(l, r, u * 2, k);
    update_tree2(l, r, u * 2 + 1, k);
    sum2[u] = sum2[u * 2] + sum2[u * 2 + 1];
}
int get_sum1(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r)
        return sum1[u];
    return get_sum1(l, r, u * 2) + get_sum1(l, r, u * 2 + 1);
}
int get_sum2(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r)
        return sum2[u];
    return get_sum2(l, r, u * 2) + get_sum2(l, r, u * 2 + 1);
}
void dfs_set(int u){
    marked[u] = 1;
    sz[u] = 1;
    st[u] = tms;
    tms += 1;
    for(int i = 0; i + 1 < lg; i++)
        par[u][i + 1] = par[par[u][i]][i];
    for(int v: conn[u])
        if(!marked[v]){
            par[v][0] = u;
            dfs_set(v);
            sz[u] += sz[v];

        }
    en[u] = tms - 1;
}
int find_pd(int u){
    u = par[u][0];
    while(col[u] == -1){
        u = par[u][0];
    }
    return u;



}
long long get_c(int a, int b){
    if(a < b)
        return 0;
    return fact[a] * (rfact[b] * rfact[a - b] % mod) % mod;

}
void add_tree(int u, int k){
    int pd = find_pd(u);
   // cout << u << ' ' << pd << endl;
    col[u] = k;
    if(u != 1){
        int x = get_sum1(st[pd] + 1, en[pd], 1);
        int d = get_sum2(st[pd] + 1, en[pd], 1);

        if(zero[pd] == 0){
            x = sz[pd] - x;
            d = col[pd] - d;
            long long f = get_c(d + x - 1, x - 1);
            ans = ans * tav(f, mod - 2) % mod;
        }
    }
  //  cout << ans << endl;
    int x = get_sum1(st[u], en[u], 1);
    int d = get_sum2(st[u], en[u], 1);
    update_tree1(st[u], st[u], 1, sz[u] - x);
    update_tree2(st[u], st[u], 1, k - d);
   // cout << st[pd] << '-' << en[pd] << endl;
    if(k < d){
        zero[u] = 1;
        tz += 1;
    }
    else{
 //       cout << x << ' ' << sz[u] << endl;
        x = sz[u] - x;
        d = k - d;
      //  cout << x << ' ' << d << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * f % mod;
    }
   // cout << ans << endl;

    if(u != 1){
        int x = get_sum1(st[pd] + 1, en[pd], 1);
        int d = get_sum2(st[pd] + 1, en[pd], 1);
        update_tree1(st[pd], st[pd], 1, sz[pd] - x);
        update_tree2(st[pd], st[pd], 1, col[pd] - d);
        if(col[pd] < d){
            tz += (1 - zero[pd]);
            zero[pd] = 1;
        }
        else{
            x = sz[pd] - x;
            d = col[pd] - d;
            tz -= zero[pd];
            zero[pd] = 0;
    //        cout << x << ' ' << d << endl;
            long long f = get_c(d + x - 1, x - 1);
            ans = ans * f % mod;
        }
    }
    //cout << ans << endl << endl;
}
void remove_tree(int u){

    int pd = find_pd(u);

    int x = get_sum1(st[pd] + 1, en[pd], 1);
    int d = get_sum2(st[pd] + 1, en[pd], 1);

    if(zero[pd] == 0){
        x = sz[pd] - x;
        d = col[pd] - d;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * tav(f, mod - 2) % mod;
    }

    x = get_sum1(st[u] + 1, en[u], 1);
    d = get_sum2(st[u] + 1, en[u], 1);

    update_tree1(st[u], st[u], 1, 0);
    update_tree2(st[u], st[u], 1, 0);
    //cout << get_sum1(1, n, 1) << endl;
    if(col[u] < d){
        tz -= zero[u];
        zero[u] = 0;
    }
    else{
        tz -= zero[u];
        zero[u] = 0;
        x = sz[u] - x;
        d = col[u] - d;
    //    cout << d << ' ' << x << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * tav(f, mod - 2) % mod;
    }
    col[u] = -1;


    x = get_sum1(st[pd] + 1, en[pd], 1);
    d = get_sum2(st[pd] + 1, en[pd], 1);

    update_tree1(st[pd], st[pd], 1, sz[pd] - x);
    update_tree2(st[pd], st[pd], 1, col[pd] - d);

    if(col[pd] < d){
        tz += (1 - zero[pd]);
        zero[pd] = 1;
    }
    else{
        tz -= (zero[pd]);
        zero[pd] = 0;
        x = sz[pd] - x;
        d = col[pd] - d;
      //  cout << d << ' ' << x << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * f % mod;
    }
}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    memset(col, -1, sizeof col);
    col[0] = 0;
    fact[0] = 1;
    for(int i = 1; i < maxn; i++)
        fact[i] = fact[i - 1] * i % mod;
    for(int i = 0; i < maxn; i++)
        rfact[i] = tav(fact[i], mod - 2) % mod;
    cin >> n >> bs;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    cout << endl;
    dfs_set(1);
    make_tree(0, n, 1);
    ans = 1;
    add_tree(1, bs);
    cout << ans << "\n";
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int a;
        int b, c;
        cin >> a;
        if(a == 1){
            cin >> b >> c;
            add_tree(b, c);
        }
        else{
            cin >> b;
            remove_tree(b);
        }
        if(tz)
            cout << 0 << "\n";
        else
            cout << ans << "\n";

    }





}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 58220 KB Output is correct
2 Correct 217 ms 58176 KB Output is correct
3 Correct 229 ms 58240 KB Output is correct
4 Correct 228 ms 58204 KB Output is correct
5 Correct 222 ms 54252 KB Output is correct
6 Correct 111 ms 22468 KB Output is correct
7 Correct 110 ms 22340 KB Output is correct
8 Correct 112 ms 22292 KB Output is correct
9 Correct 241 ms 50556 KB Output is correct
10 Correct 225 ms 50380 KB Output is correct
11 Correct 241 ms 50544 KB Output is correct
12 Correct 222 ms 49292 KB Output is correct
13 Correct 206 ms 55748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 21812 KB Output is correct
2 Correct 110 ms 21880 KB Output is correct
3 Correct 112 ms 21864 KB Output is correct
4 Correct 110 ms 21780 KB Output is correct
5 Correct 111 ms 21948 KB Output is correct
6 Correct 116 ms 22344 KB Output is correct
7 Correct 117 ms 22160 KB Output is correct
8 Correct 114 ms 22136 KB Output is correct
9 Correct 115 ms 22404 KB Output is correct
10 Correct 116 ms 22476 KB Output is correct
11 Correct 119 ms 22512 KB Output is correct
12 Correct 111 ms 22448 KB Output is correct
13 Correct 116 ms 22348 KB Output is correct
14 Correct 117 ms 22352 KB Output is correct
15 Correct 116 ms 22608 KB Output is correct
16 Correct 116 ms 22376 KB Output is correct
17 Correct 117 ms 22368 KB Output is correct
18 Correct 115 ms 22100 KB Output is correct
19 Correct 115 ms 22348 KB Output is correct
20 Correct 116 ms 22108 KB Output is correct
21 Correct 113 ms 22100 KB Output is correct
22 Correct 110 ms 21964 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 61600 KB Output is correct
2 Correct 302 ms 61928 KB Output is correct
3 Correct 255 ms 62332 KB Output is correct
4 Correct 388 ms 62580 KB Output is correct
5 Correct 517 ms 59396 KB Output is correct
6 Correct 113 ms 22544 KB Output is correct
7 Correct 112 ms 22336 KB Output is correct
8 Correct 113 ms 22420 KB Output is correct
9 Correct 546 ms 55668 KB Output is correct
10 Correct 483 ms 55296 KB Output is correct
11 Correct 471 ms 55312 KB Output is correct
12 Correct 481 ms 54704 KB Output is correct
13 Execution timed out 3043 ms 66104 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 953 ms 56628 KB Output is correct
2 Correct 881 ms 56616 KB Output is correct
3 Correct 906 ms 56696 KB Output is correct
4 Correct 849 ms 56524 KB Output is correct
5 Correct 845 ms 55316 KB Output is correct
6 Correct 813 ms 56648 KB Output is correct
7 Correct 675 ms 40364 KB Output is correct
8 Correct 722 ms 40176 KB Output is correct
9 Correct 878 ms 56708 KB Output is correct
10 Correct 838 ms 56532 KB Output is correct
11 Correct 833 ms 56640 KB Output is correct
12 Correct 716 ms 40424 KB Output is correct
13 Correct 527 ms 37228 KB Output is correct
14 Correct 660 ms 38380 KB Output is correct
15 Correct 651 ms 38620 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 58220 KB Output is correct
2 Correct 217 ms 58176 KB Output is correct
3 Correct 229 ms 58240 KB Output is correct
4 Correct 228 ms 58204 KB Output is correct
5 Correct 222 ms 54252 KB Output is correct
6 Correct 111 ms 22468 KB Output is correct
7 Correct 110 ms 22340 KB Output is correct
8 Correct 112 ms 22292 KB Output is correct
9 Correct 241 ms 50556 KB Output is correct
10 Correct 225 ms 50380 KB Output is correct
11 Correct 241 ms 50544 KB Output is correct
12 Correct 222 ms 49292 KB Output is correct
13 Correct 206 ms 55748 KB Output is correct
14 Correct 110 ms 21812 KB Output is correct
15 Correct 110 ms 21880 KB Output is correct
16 Correct 112 ms 21864 KB Output is correct
17 Correct 110 ms 21780 KB Output is correct
18 Correct 111 ms 21948 KB Output is correct
19 Correct 116 ms 22344 KB Output is correct
20 Correct 117 ms 22160 KB Output is correct
21 Correct 114 ms 22136 KB Output is correct
22 Correct 115 ms 22404 KB Output is correct
23 Correct 116 ms 22476 KB Output is correct
24 Correct 119 ms 22512 KB Output is correct
25 Correct 111 ms 22448 KB Output is correct
26 Correct 116 ms 22348 KB Output is correct
27 Correct 117 ms 22352 KB Output is correct
28 Correct 116 ms 22608 KB Output is correct
29 Correct 116 ms 22376 KB Output is correct
30 Correct 117 ms 22368 KB Output is correct
31 Correct 115 ms 22100 KB Output is correct
32 Correct 115 ms 22348 KB Output is correct
33 Correct 116 ms 22108 KB Output is correct
34 Correct 113 ms 22100 KB Output is correct
35 Correct 110 ms 21964 KB Output is correct
36 Correct 319 ms 61600 KB Output is correct
37 Correct 302 ms 61928 KB Output is correct
38 Correct 255 ms 62332 KB Output is correct
39 Correct 388 ms 62580 KB Output is correct
40 Correct 517 ms 59396 KB Output is correct
41 Correct 113 ms 22544 KB Output is correct
42 Correct 112 ms 22336 KB Output is correct
43 Correct 113 ms 22420 KB Output is correct
44 Correct 546 ms 55668 KB Output is correct
45 Correct 483 ms 55296 KB Output is correct
46 Correct 471 ms 55312 KB Output is correct
47 Correct 481 ms 54704 KB Output is correct
48 Execution timed out 3043 ms 66104 KB Time limit exceeded
49 Halted 0 ms 0 KB -