oj.uz

Submission #780644

# Submission time Handle Problem Language Result Execution time Memory
780644 2023-07-12T11:18:59 Z Sami_Massah Sumtree (INOI20_sumtree) C++17
100 / 100
 2207 ms 304248 KB 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 5e5 + 12, maxk = 2e5 + 12, lg = 18, mod = 1e9 + 7;
int n, bs, tz, tms, h[maxk], col[maxk], par[maxk][lg], sz[maxk], st[maxk], en[maxk],  sum1[maxk * 3], sum2[maxk * 3];
long long ans, fact[maxn], rfact[maxn];
set <pair<int, int>> Q[maxk * 3];
vector <int> conn[maxk];
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 update_tree1(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        sum1[u] = k;
        return;
    }
    int mid = (L + R) / 2;
    update_tree1(l, r, u * 2, k, L, mid);
    update_tree1(l, r, u * 2 + 1, k, mid + 1, R);
    sum1[u] = sum1[u * 2] + sum1[u * 2 + 1];
}
void update_tree2(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        sum2[u] = k;
        return;
    }
    int mid = (L + R) / 2;
    update_tree2(l, r, u * 2, k, L, mid);
    update_tree2(l, r, u * 2 + 1, k, mid + 1, R);
    sum2[u] = sum2[u * 2] + sum2[u * 2 + 1];
}
int get_sum1(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return 0;
    if(l <= L && R <= r)
        return sum1[u];
    int mid = (L + R) / 2;
    return get_sum1(l, r, u * 2, L, mid) + get_sum1(l, r, u * 2 + 1, mid + 1, R);
}
int get_sum2(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return 0;
    if(l <= L && R <= r)
        return sum2[u];
    int mid = (L + R) / 2;
    return get_sum2(l, r, u * 2, L, mid) + get_sum2(l, r, u * 2 + 1, mid + 1, R);
}
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;
            h[v] = h[u] + 1;
            dfs_set(v);
            sz[u] += sz[v];

        }
    en[u] = tms - 1;
}
void add_to_tree(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        Q[u].insert(make_pair(h[k], k));
        return;
    }
    int mid = (L + R) / 2;
    add_to_tree(l, r, u * 2, k, L, mid);
    add_to_tree(l, r, u * 2 + 1, k, mid + 1, R);
}
void erase_from_tree(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        Q[u].erase(make_pair(h[k], k));
        return;
    }
    int mid = (L + R) / 2;
    erase_from_tree(l, r, u * 2, k, L, mid);
    erase_from_tree(l, r, u * 2 + 1, k, mid + 1, R);
}
pair<int, int> find_pd(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return make_pair(-1, 0);
    if(l <= L && R <= r){
        if(Q[u].size() == 0)
            return make_pair(-1, 0);
        return *Q[u].rbegin();
    }
    auto x = make_pair(-1, 0);
    if(Q[u].size())
        x = *Q[u].rbegin();
    int mid = (L + R) / 2;
    return max({find_pd(l, r, u * 2, L, mid), find_pd(l, r, u * 2 + 1, mid + 1, R), x});
}
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(st[u], st[u], 1).second;
 //   cout << u << ' ' << pd << endl;
   // 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);
    add_to_tree(st[u] + 1, en[u], 1, u);
   // 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(st[u], st[u], 1).second;
   // cout << u << ' ' << pd << endl;
    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);
    erase_from_tree(st[u] + 1, en[u], 1, u);
    //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);

    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 238 ms 73624 KB Output is correct
2 Correct 237 ms 73616 KB Output is correct
3 Correct 236 ms 73676 KB Output is correct
4 Correct 248 ms 73584 KB Output is correct
5 Correct 212 ms 69632 KB Output is correct
6 Correct 121 ms 42480 KB Output is correct
7 Correct 125 ms 42160 KB Output is correct
8 Correct 121 ms 42224 KB Output is correct
9 Correct 239 ms 66016 KB Output is correct
10 Correct 262 ms 65840 KB Output is correct
11 Correct 266 ms 66100 KB Output is correct
12 Correct 239 ms 64844 KB Output is correct
13 Correct 218 ms 71292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 41712 KB Output is correct
2 Correct 121 ms 41788 KB Output is correct
3 Correct 121 ms 41816 KB Output is correct
4 Correct 121 ms 41804 KB Output is correct
5 Correct 122 ms 41824 KB Output is correct
6 Correct 125 ms 42136 KB Output is correct
7 Correct 126 ms 42108 KB Output is correct
8 Correct 125 ms 42136 KB Output is correct
9 Correct 128 ms 42360 KB Output is correct
10 Correct 130 ms 42444 KB Output is correct
11 Correct 129 ms 42536 KB Output is correct
12 Correct 122 ms 42372 KB Output is correct
13 Correct 135 ms 42464 KB Output is correct
14 Correct 135 ms 42420 KB Output is correct
15 Correct 133 ms 42844 KB Output is correct
16 Correct 128 ms 42300 KB Output is correct
17 Correct 129 ms 42444 KB Output is correct
18 Correct 132 ms 42272 KB Output is correct
19 Correct 126 ms 42284 KB Output is correct
20 Correct 125 ms 42148 KB Output is correct
21 Correct 125 ms 42072 KB Output is correct
22 Correct 122 ms 41820 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 79512 KB Output is correct
2 Correct 377 ms 84824 KB Output is correct
3 Correct 274 ms 80564 KB Output is correct
4 Correct 477 ms 93924 KB Output is correct
5 Correct 1147 ms 146028 KB Output is correct
6 Correct 126 ms 43080 KB Output is correct
7 Correct 123 ms 42272 KB Output is correct
8 Correct 126 ms 42624 KB Output is correct
9 Correct 590 ms 76724 KB Output is correct
10 Correct 564 ms 75076 KB Output is correct
11 Correct 509 ms 74684 KB Output is correct
12 Correct 603 ms 75060 KB Output is correct
13 Correct 2207 ms 303720 KB Output is correct
14 Correct 2078 ms 304240 KB Output is correct
15 Correct 2116 ms 304248 KB Output is correct
16 Correct 2077 ms 304128 KB Output is correct
17 Correct 2075 ms 304204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 72364 KB Output is correct
2 Correct 815 ms 72180 KB Output is correct
3 Correct 845 ms 72456 KB Output is correct
4 Correct 851 ms 72436 KB Output is correct
5 Correct 846 ms 71060 KB Output is correct
6 Correct 840 ms 72296 KB Output is correct
7 Correct 695 ms 58332 KB Output is correct
8 Correct 742 ms 58468 KB Output is correct
9 Correct 816 ms 72288 KB Output is correct
10 Correct 821 ms 72412 KB Output is correct
11 Correct 860 ms 72276 KB Output is correct
12 Correct 708 ms 58352 KB Output is correct
13 Correct 526 ms 55308 KB Output is correct
14 Correct 607 ms 56780 KB Output is correct
15 Correct 627 ms 56788 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 73624 KB Output is correct
2 Correct 237 ms 73616 KB Output is correct
3 Correct 236 ms 73676 KB Output is correct
4 Correct 248 ms 73584 KB Output is correct
5 Correct 212 ms 69632 KB Output is correct
6 Correct 121 ms 42480 KB Output is correct
7 Correct 125 ms 42160 KB Output is correct
8 Correct 121 ms 42224 KB Output is correct
9 Correct 239 ms 66016 KB Output is correct
10 Correct 262 ms 65840 KB Output is correct
11 Correct 266 ms 66100 KB Output is correct
12 Correct 239 ms 64844 KB Output is correct
13 Correct 218 ms 71292 KB Output is correct
14 Correct 123 ms 41712 KB Output is correct
15 Correct 121 ms 41788 KB Output is correct
16 Correct 121 ms 41816 KB Output is correct
17 Correct 121 ms 41804 KB Output is correct
18 Correct 122 ms 41824 KB Output is correct
19 Correct 125 ms 42136 KB Output is correct
20 Correct 126 ms 42108 KB Output is correct
21 Correct 125 ms 42136 KB Output is correct
22 Correct 128 ms 42360 KB Output is correct
23 Correct 130 ms 42444 KB Output is correct
24 Correct 129 ms 42536 KB Output is correct
25 Correct 122 ms 42372 KB Output is correct
26 Correct 135 ms 42464 KB Output is correct
27 Correct 135 ms 42420 KB Output is correct
28 Correct 133 ms 42844 KB Output is correct
29 Correct 128 ms 42300 KB Output is correct
30 Correct 129 ms 42444 KB Output is correct
31 Correct 132 ms 42272 KB Output is correct
32 Correct 126 ms 42284 KB Output is correct
33 Correct 125 ms 42148 KB Output is correct
34 Correct 125 ms 42072 KB Output is correct
35 Correct 122 ms 41820 KB Output is correct
36 Correct 273 ms 79512 KB Output is correct
37 Correct 377 ms 84824 KB Output is correct
38 Correct 274 ms 80564 KB Output is correct
39 Correct 477 ms 93924 KB Output is correct
40 Correct 1147 ms 146028 KB Output is correct
41 Correct 126 ms 43080 KB Output is correct
42 Correct 123 ms 42272 KB Output is correct
43 Correct 126 ms 42624 KB Output is correct
44 Correct 590 ms 76724 KB Output is correct
45 Correct 564 ms 75076 KB Output is correct
46 Correct 509 ms 74684 KB Output is correct
47 Correct 603 ms 75060 KB Output is correct
48 Correct 2207 ms 303720 KB Output is correct
49 Correct 2078 ms 304240 KB Output is correct
50 Correct 2116 ms 304248 KB Output is correct
51 Correct 2077 ms 304128 KB Output is correct
52 Correct 2075 ms 304204 KB Output is correct
53 Correct 852 ms 72364 KB Output is correct
54 Correct 815 ms 72180 KB Output is correct
55 Correct 845 ms 72456 KB Output is correct
56 Correct 851 ms 72436 KB Output is correct
57 Correct 846 ms 71060 KB Output is correct
58 Correct 840 ms 72296 KB Output is correct
59 Correct 695 ms 58332 KB Output is correct
60 Correct 742 ms 58468 KB Output is correct
61 Correct 816 ms 72288 KB Output is correct
62 Correct 821 ms 72412 KB Output is correct
63 Correct 860 ms 72276 KB Output is correct
64 Correct 708 ms 58352 KB Output is correct
65 Correct 526 ms 55308 KB Output is correct
66 Correct 607 ms 56780 KB Output is correct
67 Correct 627 ms 56788 KB Output is correct
68 Correct 129 ms 41736 KB Output is correct
69 Correct 121 ms 41732 KB Output is correct
70 Correct 993 ms 80156 KB Output is correct
71 Correct 943 ms 80052 KB Output is correct
72 Correct 954 ms 79992 KB Output is correct
73 Correct 982 ms 80200 KB Output is correct
74 Correct 1111 ms 80640 KB Output is correct
75 Correct 1043 ms 76100 KB Output is correct
76 Correct 831 ms 72308 KB Output is correct
77 Correct 861 ms 72948 KB Output is correct
78 Correct 941 ms 74024 KB Output is correct
79 Correct 963 ms 76180 KB Output is correct
80 Correct 1066 ms 75476 KB Output is correct
81 Correct 1034 ms 76392 KB Output is correct
82 Correct 690 ms 68672 KB Output is correct
83 Correct 676 ms 75868 KB Output is correct
84 Correct 731 ms 75064 KB Output is correct
85 Correct 694 ms 75068 KB Output is correct