답안 #780695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780695	2023-07-12T11:48:35 Z	Sami_Massah	Sumtree (INOI20_sumtree)	C++17	100 / 100	2059 ms	290284 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, qsum, h[maxk], col[maxk],  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 v: conn[u])
        if(!marked[v]){

            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){
        qsum += 1;
        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){
        qsum -= 1;
        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(qsum > 4e6)
      ///      return 0;
        if(tz)
            cout << 0 << "\n";
        else
            cout << ans << "\n";

    }





}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	57580 KB	Output is correct
2	Correct	269 ms	57608 KB	Output is correct
3	Correct	228 ms	57512 KB	Output is correct
4	Correct	225 ms	57988 KB	Output is correct
5	Correct	229 ms	55324 KB	Output is correct
6	Correct	129 ms	42184 KB	Output is correct
7	Correct	131 ms	42004 KB	Output is correct
8	Correct	128 ms	41948 KB	Output is correct
9	Correct	225 ms	52788 KB	Output is correct
10	Correct	273 ms	52804 KB	Output is correct
11	Correct	227 ms	52896 KB	Output is correct
12	Correct	224 ms	52568 KB	Output is correct
13	Correct	187 ms	58252 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	138 ms	41824 KB	Output is correct
2	Correct	132 ms	41792 KB	Output is correct
3	Correct	128 ms	41728 KB	Output is correct
4	Correct	124 ms	41832 KB	Output is correct
5	Correct	127 ms	41816 KB	Output is correct
6	Correct	130 ms	41992 KB	Output is correct
7	Correct	132 ms	42044 KB	Output is correct
8	Correct	129 ms	42004 KB	Output is correct
9	Correct	133 ms	42080 KB	Output is correct
10	Correct	132 ms	42196 KB	Output is correct
11	Correct	138 ms	42268 KB	Output is correct
12	Correct	126 ms	42108 KB	Output is correct
13	Correct	133 ms	42216 KB	Output is correct
14	Correct	136 ms	42208 KB	Output is correct
15	Correct	140 ms	42636 KB	Output is correct
16	Correct	133 ms	42152 KB	Output is correct
17	Correct	135 ms	42284 KB	Output is correct
18	Correct	133 ms	42244 KB	Output is correct
19	Correct	135 ms	42072 KB	Output is correct
20	Correct	138 ms	41936 KB	Output is correct
21	Correct	130 ms	41992 KB	Output is correct
22	Correct	128 ms	41948 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	66148 KB	Output is correct
2	Correct	362 ms	71512 KB	Output is correct
3	Correct	261 ms	67004 KB	Output is correct
4	Correct	463 ms	80828 KB	Output is correct
5	Correct	1170 ms	134512 KB	Output is correct
6	Correct	129 ms	42896 KB	Output is correct
7	Correct	124 ms	42072 KB	Output is correct
8	Correct	125 ms	42388 KB	Output is correct
9	Correct	547 ms	65644 KB	Output is correct
10	Correct	500 ms	63928 KB	Output is correct
11	Correct	449 ms	63224 KB	Output is correct
12	Correct	483 ms	64160 KB	Output is correct
13	Correct	2043 ms	289956 KB	Output is correct
14	Correct	2056 ms	290244 KB	Output is correct
15	Correct	2047 ms	290284 KB	Output is correct
16	Correct	2059 ms	290248 KB	Output is correct
17	Correct	2036 ms	290112 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	788 ms	61420 KB	Output is correct
2	Correct	774 ms	61360 KB	Output is correct
3	Correct	806 ms	61396 KB	Output is correct
4	Correct	857 ms	61624 KB	Output is correct
5	Correct	778 ms	61056 KB	Output is correct
6	Correct	802 ms	61628 KB	Output is correct
7	Correct	681 ms	53616 KB	Output is correct
8	Correct	693 ms	53872 KB	Output is correct
9	Correct	836 ms	61560 KB	Output is correct
10	Correct	778 ms	61588 KB	Output is correct
11	Correct	815 ms	61564 KB	Output is correct
12	Correct	669 ms	53832 KB	Output is correct
13	Correct	509 ms	50896 KB	Output is correct
14	Correct	616 ms	52164 KB	Output is correct
15	Correct	622 ms	52312 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	57580 KB	Output is correct
2	Correct	269 ms	57608 KB	Output is correct
3	Correct	228 ms	57512 KB	Output is correct
4	Correct	225 ms	57988 KB	Output is correct
5	Correct	229 ms	55324 KB	Output is correct
6	Correct	129 ms	42184 KB	Output is correct
7	Correct	131 ms	42004 KB	Output is correct
8	Correct	128 ms	41948 KB	Output is correct
9	Correct	225 ms	52788 KB	Output is correct
10	Correct	273 ms	52804 KB	Output is correct
11	Correct	227 ms	52896 KB	Output is correct
12	Correct	224 ms	52568 KB	Output is correct
13	Correct	187 ms	58252 KB	Output is correct
14	Correct	138 ms	41824 KB	Output is correct
15	Correct	132 ms	41792 KB	Output is correct
16	Correct	128 ms	41728 KB	Output is correct
17	Correct	124 ms	41832 KB	Output is correct
18	Correct	127 ms	41816 KB	Output is correct
19	Correct	130 ms	41992 KB	Output is correct
20	Correct	132 ms	42044 KB	Output is correct
21	Correct	129 ms	42004 KB	Output is correct
22	Correct	133 ms	42080 KB	Output is correct
23	Correct	132 ms	42196 KB	Output is correct
24	Correct	138 ms	42268 KB	Output is correct
25	Correct	126 ms	42108 KB	Output is correct
26	Correct	133 ms	42216 KB	Output is correct
27	Correct	136 ms	42208 KB	Output is correct
28	Correct	140 ms	42636 KB	Output is correct
29	Correct	133 ms	42152 KB	Output is correct
30	Correct	135 ms	42284 KB	Output is correct
31	Correct	133 ms	42244 KB	Output is correct
32	Correct	135 ms	42072 KB	Output is correct
33	Correct	138 ms	41936 KB	Output is correct
34	Correct	130 ms	41992 KB	Output is correct
35	Correct	128 ms	41948 KB	Output is correct
36	Correct	261 ms	66148 KB	Output is correct
37	Correct	362 ms	71512 KB	Output is correct
38	Correct	261 ms	67004 KB	Output is correct
39	Correct	463 ms	80828 KB	Output is correct
40	Correct	1170 ms	134512 KB	Output is correct
41	Correct	129 ms	42896 KB	Output is correct
42	Correct	124 ms	42072 KB	Output is correct
43	Correct	125 ms	42388 KB	Output is correct
44	Correct	547 ms	65644 KB	Output is correct
45	Correct	500 ms	63928 KB	Output is correct
46	Correct	449 ms	63224 KB	Output is correct
47	Correct	483 ms	64160 KB	Output is correct
48	Correct	2043 ms	289956 KB	Output is correct
49	Correct	2056 ms	290244 KB	Output is correct
50	Correct	2047 ms	290284 KB	Output is correct
51	Correct	2059 ms	290248 KB	Output is correct
52	Correct	2036 ms	290112 KB	Output is correct
53	Correct	788 ms	61420 KB	Output is correct
54	Correct	774 ms	61360 KB	Output is correct
55	Correct	806 ms	61396 KB	Output is correct
56	Correct	857 ms	61624 KB	Output is correct
57	Correct	778 ms	61056 KB	Output is correct
58	Correct	802 ms	61628 KB	Output is correct
59	Correct	681 ms	53616 KB	Output is correct
60	Correct	693 ms	53872 KB	Output is correct
61	Correct	836 ms	61560 KB	Output is correct
62	Correct	778 ms	61588 KB	Output is correct
63	Correct	815 ms	61564 KB	Output is correct
64	Correct	669 ms	53832 KB	Output is correct
65	Correct	509 ms	50896 KB	Output is correct
66	Correct	616 ms	52164 KB	Output is correct
67	Correct	622 ms	52312 KB	Output is correct
68	Correct	124 ms	41712 KB	Output is correct
69	Correct	121 ms	41832 KB	Output is correct
70	Correct	874 ms	67704 KB	Output is correct
71	Correct	995 ms	67760 KB	Output is correct
72	Correct	897 ms	67812 KB	Output is correct
73	Correct	899 ms	67792 KB	Output is correct
74	Correct	1089 ms	68280 KB	Output is correct
75	Correct	1055 ms	64692 KB	Output is correct
76	Correct	826 ms	61752 KB	Output is correct
77	Correct	797 ms	62416 KB	Output is correct
78	Correct	863 ms	63424 KB	Output is correct
79	Correct	919 ms	64848 KB	Output is correct
80	Correct	1000 ms	64876 KB	Output is correct
81	Correct	1078 ms	65232 KB	Output is correct
82	Correct	628 ms	58192 KB	Output is correct
83	Correct	646 ms	63564 KB	Output is correct
84	Correct	701 ms	62928 KB	Output is correct
85	Correct	667 ms	62796 KB	Output is correct