답안 #780638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780638	2023-07-12T11:13:17 Z	Sami_Massah	Sumtree (INOI20_sumtree)	C++17	100 / 100	2217 ms	307616 KB

Main

#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], L[maxk * 3], R[maxk * 3], 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 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;
            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){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        Q[u].insert(make_pair(h[k], k));
        return;
    }
    add_to_tree(l, r, u * 2, k);
    add_to_tree(l, r, u * 2 + 1, k);
}
void erase_from_tree(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        Q[u].erase(make_pair(h[k], k));
        return;
    }
    erase_from_tree(l, r, u * 2, k);
    erase_from_tree(l, r, u * 2 + 1, k);
}
pair<int, int> find_pd(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return make_pair(-1, 0);
    if(l <= L[u] && R[u] <= 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();
    return max({find_pd(l, r, u * 2), find_pd(l, r, u * 2 + 1), 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);
    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

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	77296 KB	Output is correct
2	Correct	226 ms	77316 KB	Output is correct
3	Correct	226 ms	77320 KB	Output is correct
4	Correct	250 ms	77404 KB	Output is correct
5	Correct	193 ms	73420 KB	Output is correct
6	Correct	120 ms	42488 KB	Output is correct
7	Correct	126 ms	42184 KB	Output is correct
8	Correct	122 ms	42336 KB	Output is correct
9	Correct	240 ms	69736 KB	Output is correct
10	Correct	269 ms	69600 KB	Output is correct
11	Correct	231 ms	69724 KB	Output is correct
12	Correct	219 ms	68568 KB	Output is correct
13	Correct	216 ms	75036 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	41808 KB	Output is correct
2	Correct	120 ms	41776 KB	Output is correct
3	Correct	117 ms	41748 KB	Output is correct
4	Correct	119 ms	41800 KB	Output is correct
5	Correct	124 ms	41928 KB	Output is correct
6	Correct	123 ms	42168 KB	Output is correct
7	Correct	126 ms	42128 KB	Output is correct
8	Correct	124 ms	42128 KB	Output is correct
9	Correct	126 ms	42360 KB	Output is correct
10	Correct	131 ms	42516 KB	Output is correct
11	Correct	134 ms	42508 KB	Output is correct
12	Correct	120 ms	42424 KB	Output is correct
13	Correct	128 ms	42444 KB	Output is correct
14	Correct	134 ms	42464 KB	Output is correct
15	Correct	130 ms	42884 KB	Output is correct
16	Correct	126 ms	42320 KB	Output is correct
17	Correct	128 ms	42428 KB	Output is correct
18	Correct	127 ms	42308 KB	Output is correct
19	Correct	130 ms	42288 KB	Output is correct
20	Correct	126 ms	42108 KB	Output is correct
21	Correct	124 ms	42100 KB	Output is correct
22	Correct	125 ms	41912 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	274 ms	83288 KB	Output is correct
2	Correct	382 ms	88504 KB	Output is correct
3	Correct	307 ms	84160 KB	Output is correct
4	Correct	494 ms	97660 KB	Output is correct
5	Correct	1217 ms	149676 KB	Output is correct
6	Correct	125 ms	43152 KB	Output is correct
7	Correct	122 ms	42376 KB	Output is correct
8	Correct	124 ms	42680 KB	Output is correct
9	Correct	620 ms	80492 KB	Output is correct
10	Correct	566 ms	78744 KB	Output is correct
11	Correct	496 ms	78192 KB	Output is correct
12	Correct	635 ms	78804 KB	Output is correct
13	Correct	2176 ms	307616 KB	Output is correct
14	Correct	2078 ms	307572 KB	Output is correct
15	Correct	2217 ms	307536 KB	Output is correct
16	Correct	2092 ms	307504 KB	Output is correct
17	Correct	2067 ms	307532 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	922 ms	75780 KB	Output is correct
2	Correct	943 ms	75756 KB	Output is correct
3	Correct	941 ms	75828 KB	Output is correct
4	Correct	908 ms	75796 KB	Output is correct
5	Correct	874 ms	74556 KB	Output is correct
6	Correct	943 ms	75820 KB	Output is correct
7	Correct	879 ms	59904 KB	Output is correct
8	Correct	847 ms	59884 KB	Output is correct
9	Correct	943 ms	75852 KB	Output is correct
10	Correct	889 ms	75816 KB	Output is correct
11	Correct	929 ms	75804 KB	Output is correct
12	Correct	736 ms	59868 KB	Output is correct
13	Correct	572 ms	56756 KB	Output is correct
14	Correct	685 ms	58092 KB	Output is correct
15	Correct	666 ms	58240 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	77296 KB	Output is correct
2	Correct	226 ms	77316 KB	Output is correct
3	Correct	226 ms	77320 KB	Output is correct
4	Correct	250 ms	77404 KB	Output is correct
5	Correct	193 ms	73420 KB	Output is correct
6	Correct	120 ms	42488 KB	Output is correct
7	Correct	126 ms	42184 KB	Output is correct
8	Correct	122 ms	42336 KB	Output is correct
9	Correct	240 ms	69736 KB	Output is correct
10	Correct	269 ms	69600 KB	Output is correct
11	Correct	231 ms	69724 KB	Output is correct
12	Correct	219 ms	68568 KB	Output is correct
13	Correct	216 ms	75036 KB	Output is correct
14	Correct	117 ms	41808 KB	Output is correct
15	Correct	120 ms	41776 KB	Output is correct
16	Correct	117 ms	41748 KB	Output is correct
17	Correct	119 ms	41800 KB	Output is correct
18	Correct	124 ms	41928 KB	Output is correct
19	Correct	123 ms	42168 KB	Output is correct
20	Correct	126 ms	42128 KB	Output is correct
21	Correct	124 ms	42128 KB	Output is correct
22	Correct	126 ms	42360 KB	Output is correct
23	Correct	131 ms	42516 KB	Output is correct
24	Correct	134 ms	42508 KB	Output is correct
25	Correct	120 ms	42424 KB	Output is correct
26	Correct	128 ms	42444 KB	Output is correct
27	Correct	134 ms	42464 KB	Output is correct
28	Correct	130 ms	42884 KB	Output is correct
29	Correct	126 ms	42320 KB	Output is correct
30	Correct	128 ms	42428 KB	Output is correct
31	Correct	127 ms	42308 KB	Output is correct
32	Correct	130 ms	42288 KB	Output is correct
33	Correct	126 ms	42108 KB	Output is correct
34	Correct	124 ms	42100 KB	Output is correct
35	Correct	125 ms	41912 KB	Output is correct
36	Correct	274 ms	83288 KB	Output is correct
37	Correct	382 ms	88504 KB	Output is correct
38	Correct	307 ms	84160 KB	Output is correct
39	Correct	494 ms	97660 KB	Output is correct
40	Correct	1217 ms	149676 KB	Output is correct
41	Correct	125 ms	43152 KB	Output is correct
42	Correct	122 ms	42376 KB	Output is correct
43	Correct	124 ms	42680 KB	Output is correct
44	Correct	620 ms	80492 KB	Output is correct
45	Correct	566 ms	78744 KB	Output is correct
46	Correct	496 ms	78192 KB	Output is correct
47	Correct	635 ms	78804 KB	Output is correct
48	Correct	2176 ms	307616 KB	Output is correct
49	Correct	2078 ms	307572 KB	Output is correct
50	Correct	2217 ms	307536 KB	Output is correct
51	Correct	2092 ms	307504 KB	Output is correct
52	Correct	2067 ms	307532 KB	Output is correct
53	Correct	922 ms	75780 KB	Output is correct
54	Correct	943 ms	75756 KB	Output is correct
55	Correct	941 ms	75828 KB	Output is correct
56	Correct	908 ms	75796 KB	Output is correct
57	Correct	874 ms	74556 KB	Output is correct
58	Correct	943 ms	75820 KB	Output is correct
59	Correct	879 ms	59904 KB	Output is correct
60	Correct	847 ms	59884 KB	Output is correct
61	Correct	943 ms	75852 KB	Output is correct
62	Correct	889 ms	75816 KB	Output is correct
63	Correct	929 ms	75804 KB	Output is correct
64	Correct	736 ms	59868 KB	Output is correct
65	Correct	572 ms	56756 KB	Output is correct
66	Correct	685 ms	58092 KB	Output is correct
67	Correct	666 ms	58240 KB	Output is correct
68	Correct	119 ms	41836 KB	Output is correct
69	Correct	120 ms	41764 KB	Output is correct
70	Correct	1000 ms	83448 KB	Output is correct
71	Correct	977 ms	83472 KB	Output is correct
72	Correct	993 ms	83472 KB	Output is correct
73	Correct	1111 ms	83436 KB	Output is correct
74	Correct	1231 ms	83780 KB	Output is correct
75	Correct	1106 ms	79520 KB	Output is correct
76	Correct	893 ms	75824 KB	Output is correct
77	Correct	991 ms	76368 KB	Output is correct
78	Correct	1010 ms	77452 KB	Output is correct
79	Correct	1047 ms	79640 KB	Output is correct
80	Correct	1154 ms	78884 KB	Output is correct
81	Correct	1128 ms	79932 KB	Output is correct
82	Correct	770 ms	72028 KB	Output is correct
83	Correct	693 ms	79232 KB	Output is correct
84	Correct	761 ms	78448 KB	Output is correct
85	Correct	710 ms	78348 KB	Output is correct