답안 #780604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780604	2023-07-12T10:47:20 Z	Sami_Massah	Sumtree (INOI20_sumtree)	C++17	100 / 100	2305 ms	322456 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 * 4], R[maxk * 4], sum1[maxk * 4], sum2[maxk * 4];
long long ans, fact[maxn], rfact[maxn];
set <pair<int, int>> Q[maxk * 4];
vector <int> conn[maxk];
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;
            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	249 ms	89236 KB	Output is correct
2	Correct	233 ms	89204 KB	Output is correct
3	Correct	262 ms	89232 KB	Output is correct
4	Correct	262 ms	89164 KB	Output is correct
5	Correct	207 ms	85252 KB	Output is correct
6	Correct	131 ms	51928 KB	Output is correct
7	Correct	127 ms	51724 KB	Output is correct
8	Correct	127 ms	51768 KB	Output is correct
9	Correct	238 ms	81568 KB	Output is correct
10	Correct	240 ms	81396 KB	Output is correct
11	Correct	274 ms	81552 KB	Output is correct
12	Correct	244 ms	80164 KB	Output is correct
13	Correct	224 ms	86572 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	51180 KB	Output is correct
2	Correct	124 ms	51148 KB	Output is correct
3	Correct	124 ms	51236 KB	Output is correct
4	Correct	124 ms	51192 KB	Output is correct
5	Correct	130 ms	51356 KB	Output is correct
6	Correct	128 ms	51680 KB	Output is correct
7	Correct	128 ms	51556 KB	Output is correct
8	Correct	129 ms	51544 KB	Output is correct
9	Correct	138 ms	51856 KB	Output is correct
10	Correct	138 ms	51980 KB	Output is correct
11	Correct	133 ms	52056 KB	Output is correct
12	Correct	126 ms	51808 KB	Output is correct
13	Correct	133 ms	51936 KB	Output is correct
14	Correct	136 ms	51928 KB	Output is correct
15	Correct	135 ms	52344 KB	Output is correct
16	Correct	130 ms	51788 KB	Output is correct
17	Correct	133 ms	51896 KB	Output is correct
18	Correct	133 ms	51720 KB	Output is correct
19	Correct	133 ms	51856 KB	Output is correct
20	Correct	129 ms	51576 KB	Output is correct
21	Correct	127 ms	51532 KB	Output is correct
22	Correct	123 ms	51280 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	291 ms	95128 KB	Output is correct
2	Correct	364 ms	100508 KB	Output is correct
3	Correct	307 ms	96148 KB	Output is correct
4	Correct	508 ms	109980 KB	Output is correct
5	Correct	1148 ms	162908 KB	Output is correct
6	Correct	130 ms	52688 KB	Output is correct
7	Correct	126 ms	51764 KB	Output is correct
8	Correct	130 ms	52024 KB	Output is correct
9	Correct	646 ms	93228 KB	Output is correct
10	Correct	608 ms	91432 KB	Output is correct
11	Correct	529 ms	90800 KB	Output is correct
12	Correct	608 ms	91880 KB	Output is correct
13	Correct	2140 ms	322324 KB	Output is correct
14	Correct	2130 ms	322424 KB	Output is correct
15	Correct	2187 ms	322456 KB	Output is correct
16	Correct	2206 ms	322336 KB	Output is correct
17	Correct	2305 ms	322344 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1020 ms	89612 KB	Output is correct
2	Correct	1022 ms	89628 KB	Output is correct
3	Correct	934 ms	89552 KB	Output is correct
4	Correct	997 ms	89672 KB	Output is correct
5	Correct	905 ms	88188 KB	Output is correct
6	Correct	937 ms	89544 KB	Output is correct
7	Correct	783 ms	72076 KB	Output is correct
8	Correct	808 ms	72268 KB	Output is correct
9	Correct	975 ms	89596 KB	Output is correct
10	Correct	909 ms	89748 KB	Output is correct
11	Correct	913 ms	89764 KB	Output is correct
12	Correct	821 ms	72284 KB	Output is correct
13	Correct	571 ms	69352 KB	Output is correct
14	Correct	690 ms	70808 KB	Output is correct
15	Correct	678 ms	71052 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	249 ms	89236 KB	Output is correct
2	Correct	233 ms	89204 KB	Output is correct
3	Correct	262 ms	89232 KB	Output is correct
4	Correct	262 ms	89164 KB	Output is correct
5	Correct	207 ms	85252 KB	Output is correct
6	Correct	131 ms	51928 KB	Output is correct
7	Correct	127 ms	51724 KB	Output is correct
8	Correct	127 ms	51768 KB	Output is correct
9	Correct	238 ms	81568 KB	Output is correct
10	Correct	240 ms	81396 KB	Output is correct
11	Correct	274 ms	81552 KB	Output is correct
12	Correct	244 ms	80164 KB	Output is correct
13	Correct	224 ms	86572 KB	Output is correct
14	Correct	130 ms	51180 KB	Output is correct
15	Correct	124 ms	51148 KB	Output is correct
16	Correct	124 ms	51236 KB	Output is correct
17	Correct	124 ms	51192 KB	Output is correct
18	Correct	130 ms	51356 KB	Output is correct
19	Correct	128 ms	51680 KB	Output is correct
20	Correct	128 ms	51556 KB	Output is correct
21	Correct	129 ms	51544 KB	Output is correct
22	Correct	138 ms	51856 KB	Output is correct
23	Correct	138 ms	51980 KB	Output is correct
24	Correct	133 ms	52056 KB	Output is correct
25	Correct	126 ms	51808 KB	Output is correct
26	Correct	133 ms	51936 KB	Output is correct
27	Correct	136 ms	51928 KB	Output is correct
28	Correct	135 ms	52344 KB	Output is correct
29	Correct	130 ms	51788 KB	Output is correct
30	Correct	133 ms	51896 KB	Output is correct
31	Correct	133 ms	51720 KB	Output is correct
32	Correct	133 ms	51856 KB	Output is correct
33	Correct	129 ms	51576 KB	Output is correct
34	Correct	127 ms	51532 KB	Output is correct
35	Correct	123 ms	51280 KB	Output is correct
36	Correct	291 ms	95128 KB	Output is correct
37	Correct	364 ms	100508 KB	Output is correct
38	Correct	307 ms	96148 KB	Output is correct
39	Correct	508 ms	109980 KB	Output is correct
40	Correct	1148 ms	162908 KB	Output is correct
41	Correct	130 ms	52688 KB	Output is correct
42	Correct	126 ms	51764 KB	Output is correct
43	Correct	130 ms	52024 KB	Output is correct
44	Correct	646 ms	93228 KB	Output is correct
45	Correct	608 ms	91432 KB	Output is correct
46	Correct	529 ms	90800 KB	Output is correct
47	Correct	608 ms	91880 KB	Output is correct
48	Correct	2140 ms	322324 KB	Output is correct
49	Correct	2130 ms	322424 KB	Output is correct
50	Correct	2187 ms	322456 KB	Output is correct
51	Correct	2206 ms	322336 KB	Output is correct
52	Correct	2305 ms	322344 KB	Output is correct
53	Correct	1020 ms	89612 KB	Output is correct
54	Correct	1022 ms	89628 KB	Output is correct
55	Correct	934 ms	89552 KB	Output is correct
56	Correct	997 ms	89672 KB	Output is correct
57	Correct	905 ms	88188 KB	Output is correct
58	Correct	937 ms	89544 KB	Output is correct
59	Correct	783 ms	72076 KB	Output is correct
60	Correct	808 ms	72268 KB	Output is correct
61	Correct	975 ms	89596 KB	Output is correct
62	Correct	909 ms	89748 KB	Output is correct
63	Correct	913 ms	89764 KB	Output is correct
64	Correct	821 ms	72284 KB	Output is correct
65	Correct	571 ms	69352 KB	Output is correct
66	Correct	690 ms	70808 KB	Output is correct
67	Correct	678 ms	71052 KB	Output is correct
68	Correct	124 ms	51244 KB	Output is correct
69	Correct	125 ms	51252 KB	Output is correct
70	Correct	1027 ms	97432 KB	Output is correct
71	Correct	990 ms	97524 KB	Output is correct
72	Correct	985 ms	97500 KB	Output is correct
73	Correct	1008 ms	97504 KB	Output is correct
74	Correct	1191 ms	97728 KB	Output is correct
75	Correct	1119 ms	93712 KB	Output is correct
76	Correct	891 ms	89844 KB	Output is correct
77	Correct	934 ms	90076 KB	Output is correct
78	Correct	992 ms	91128 KB	Output is correct
79	Correct	1016 ms	93508 KB	Output is correct
80	Correct	1204 ms	92484 KB	Output is correct
81	Correct	1120 ms	93536 KB	Output is correct
82	Correct	737 ms	86024 KB	Output is correct
83	Correct	712 ms	93172 KB	Output is correct
84	Correct	758 ms	92436 KB	Output is correct
85	Correct	706 ms	92496 KB	Output is correct