답안 #780610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780610	2023-07-12T10:49:04 Z	Sami_Massah	Sumtree (INOI20_sumtree)	C++17	100 / 100	2230 ms	316968 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];
multiset <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(h[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(Q[u].lower_bound(h[k]));
        return;
    }
    erase_from_tree(l, r, u * 2, k);
    erase_from_tree(l, r, u * 2 + 1, k);
}
int find_pd(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return -1;
    if(l <= L[u] && R[u] <= r){
        if(Q[u].size() == 0)
            return -1;
        return *Q[u].rbegin();
    }
    auto x = -1;
    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;

}
int kpar(int u, int k){
    for(int i = 0; i < lg; i++)
        if((k >> i) & 1)
            u = par[u][i];
    return u;

}
void add_tree(int u, int k){
    int pd = find_pd(st[u], st[u], 1);
   // cout << pd << endl;
    pd = kpar(u, h[u] - pd);
 //   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);
    pd = kpar(u, h[u] - pd);
   // 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	232 ms	86776 KB	Output is correct
2	Correct	241 ms	86728 KB	Output is correct
3	Correct	256 ms	86684 KB	Output is correct
4	Correct	246 ms	86704 KB	Output is correct
5	Correct	223 ms	82768 KB	Output is correct
6	Correct	130 ms	51916 KB	Output is correct
7	Correct	131 ms	51588 KB	Output is correct
8	Correct	131 ms	51636 KB	Output is correct
9	Correct	286 ms	79048 KB	Output is correct
10	Correct	253 ms	79028 KB	Output is correct
11	Correct	251 ms	79040 KB	Output is correct
12	Correct	234 ms	77864 KB	Output is correct
13	Correct	218 ms	84416 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	51220 KB	Output is correct
2	Correct	133 ms	51248 KB	Output is correct
3	Correct	127 ms	51204 KB	Output is correct
4	Correct	127 ms	51148 KB	Output is correct
5	Correct	128 ms	51244 KB	Output is correct
6	Correct	130 ms	51636 KB	Output is correct
7	Correct	131 ms	51548 KB	Output is correct
8	Correct	132 ms	51560 KB	Output is correct
9	Correct	134 ms	51792 KB	Output is correct
10	Correct	137 ms	51840 KB	Output is correct
11	Correct	135 ms	51896 KB	Output is correct
12	Correct	128 ms	51812 KB	Output is correct
13	Correct	139 ms	51864 KB	Output is correct
14	Correct	140 ms	51928 KB	Output is correct
15	Correct	139 ms	52248 KB	Output is correct
16	Correct	134 ms	51724 KB	Output is correct
17	Correct	138 ms	51832 KB	Output is correct
18	Correct	135 ms	51660 KB	Output is correct
19	Correct	135 ms	51808 KB	Output is correct
20	Correct	130 ms	51488 KB	Output is correct
21	Correct	141 ms	51480 KB	Output is correct
22	Correct	128 ms	51324 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	289 ms	92656 KB	Output is correct
2	Correct	391 ms	97824 KB	Output is correct
3	Correct	292 ms	93572 KB	Output is correct
4	Correct	530 ms	107056 KB	Output is correct
5	Correct	1177 ms	159012 KB	Output is correct
6	Correct	134 ms	52520 KB	Output is correct
7	Correct	132 ms	51672 KB	Output is correct
8	Correct	137 ms	52096 KB	Output is correct
9	Correct	676 ms	89820 KB	Output is correct
10	Correct	594 ms	88208 KB	Output is correct
11	Correct	551 ms	87604 KB	Output is correct
12	Correct	581 ms	88280 KB	Output is correct
13	Correct	2209 ms	316956 KB	Output is correct
14	Correct	2214 ms	316968 KB	Output is correct
15	Correct	2225 ms	316860 KB	Output is correct
16	Correct	2189 ms	316932 KB	Output is correct
17	Correct	2230 ms	316860 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	998 ms	85172 KB	Output is correct
2	Correct	1002 ms	85124 KB	Output is correct
3	Correct	1002 ms	85120 KB	Output is correct
4	Correct	992 ms	85136 KB	Output is correct
5	Correct	982 ms	83884 KB	Output is correct
6	Correct	987 ms	85148 KB	Output is correct
7	Correct	836 ms	69252 KB	Output is correct
8	Correct	849 ms	69308 KB	Output is correct
9	Correct	1029 ms	85192 KB	Output is correct
10	Correct	930 ms	85152 KB	Output is correct
11	Correct	901 ms	85156 KB	Output is correct
12	Correct	752 ms	69236 KB	Output is correct
13	Correct	550 ms	66196 KB	Output is correct
14	Correct	657 ms	67440 KB	Output is correct
15	Correct	678 ms	67672 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	86776 KB	Output is correct
2	Correct	241 ms	86728 KB	Output is correct
3	Correct	256 ms	86684 KB	Output is correct
4	Correct	246 ms	86704 KB	Output is correct
5	Correct	223 ms	82768 KB	Output is correct
6	Correct	130 ms	51916 KB	Output is correct
7	Correct	131 ms	51588 KB	Output is correct
8	Correct	131 ms	51636 KB	Output is correct
9	Correct	286 ms	79048 KB	Output is correct
10	Correct	253 ms	79028 KB	Output is correct
11	Correct	251 ms	79040 KB	Output is correct
12	Correct	234 ms	77864 KB	Output is correct
13	Correct	218 ms	84416 KB	Output is correct
14	Correct	131 ms	51220 KB	Output is correct
15	Correct	133 ms	51248 KB	Output is correct
16	Correct	127 ms	51204 KB	Output is correct
17	Correct	127 ms	51148 KB	Output is correct
18	Correct	128 ms	51244 KB	Output is correct
19	Correct	130 ms	51636 KB	Output is correct
20	Correct	131 ms	51548 KB	Output is correct
21	Correct	132 ms	51560 KB	Output is correct
22	Correct	134 ms	51792 KB	Output is correct
23	Correct	137 ms	51840 KB	Output is correct
24	Correct	135 ms	51896 KB	Output is correct
25	Correct	128 ms	51812 KB	Output is correct
26	Correct	139 ms	51864 KB	Output is correct
27	Correct	140 ms	51928 KB	Output is correct
28	Correct	139 ms	52248 KB	Output is correct
29	Correct	134 ms	51724 KB	Output is correct
30	Correct	138 ms	51832 KB	Output is correct
31	Correct	135 ms	51660 KB	Output is correct
32	Correct	135 ms	51808 KB	Output is correct
33	Correct	130 ms	51488 KB	Output is correct
34	Correct	141 ms	51480 KB	Output is correct
35	Correct	128 ms	51324 KB	Output is correct
36	Correct	289 ms	92656 KB	Output is correct
37	Correct	391 ms	97824 KB	Output is correct
38	Correct	292 ms	93572 KB	Output is correct
39	Correct	530 ms	107056 KB	Output is correct
40	Correct	1177 ms	159012 KB	Output is correct
41	Correct	134 ms	52520 KB	Output is correct
42	Correct	132 ms	51672 KB	Output is correct
43	Correct	137 ms	52096 KB	Output is correct
44	Correct	676 ms	89820 KB	Output is correct
45	Correct	594 ms	88208 KB	Output is correct
46	Correct	551 ms	87604 KB	Output is correct
47	Correct	581 ms	88280 KB	Output is correct
48	Correct	2209 ms	316956 KB	Output is correct
49	Correct	2214 ms	316968 KB	Output is correct
50	Correct	2225 ms	316860 KB	Output is correct
51	Correct	2189 ms	316932 KB	Output is correct
52	Correct	2230 ms	316860 KB	Output is correct
53	Correct	998 ms	85172 KB	Output is correct
54	Correct	1002 ms	85124 KB	Output is correct
55	Correct	1002 ms	85120 KB	Output is correct
56	Correct	992 ms	85136 KB	Output is correct
57	Correct	982 ms	83884 KB	Output is correct
58	Correct	987 ms	85148 KB	Output is correct
59	Correct	836 ms	69252 KB	Output is correct
60	Correct	849 ms	69308 KB	Output is correct
61	Correct	1029 ms	85192 KB	Output is correct
62	Correct	930 ms	85152 KB	Output is correct
63	Correct	901 ms	85156 KB	Output is correct
64	Correct	752 ms	69236 KB	Output is correct
65	Correct	550 ms	66196 KB	Output is correct
66	Correct	657 ms	67440 KB	Output is correct
67	Correct	678 ms	67672 KB	Output is correct
68	Correct	128 ms	51416 KB	Output is correct
69	Correct	124 ms	51172 KB	Output is correct
70	Correct	1050 ms	92756 KB	Output is correct
71	Correct	1062 ms	92712 KB	Output is correct
72	Correct	1067 ms	92740 KB	Output is correct
73	Correct	1097 ms	92944 KB	Output is correct
74	Correct	1228 ms	93252 KB	Output is correct
75	Correct	1205 ms	88928 KB	Output is correct
76	Correct	948 ms	85152 KB	Output is correct
77	Correct	1053 ms	85624 KB	Output is correct
78	Correct	1171 ms	86836 KB	Output is correct
79	Correct	1181 ms	88916 KB	Output is correct
80	Correct	1269 ms	88256 KB	Output is correct
81	Correct	1275 ms	89048 KB	Output is correct
82	Correct	747 ms	81412 KB	Output is correct
83	Correct	730 ms	88496 KB	Output is correct
84	Correct	813 ms	87788 KB	Output is correct
85	Correct	761 ms	87820 KB	Output is correct