QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525955#6340. TourismQwerty12320 1070ms25424kbC++235.8kb2024-08-21 05:19:002024-08-21 05:19:03

Judging History

你现在查看的是最新测评结果

  • [2024-08-21 05:19:03]
  • 评测
  • 测评结果:0
  • 用时:1070ms
  • 内存:25424kb
  • [2024-08-21 05:19:00]
  • 提交

answer

#include <bits/stdc++.h>

struct ST {
    std::vector<std::vector<int>> data;

    ST(const std::vector<int>& vec) {
        int lg = std::bit_width(vec.size());
        data.resize(lg);
        data[0] = vec;
        for (int k = 1; k < lg; k++) {
            data[k].resize(vec.size() - (1 << k) + 1);
            for (int i = 0; i < data[k].size(); i++) {
                data[k][i] = std::min(data[k - 1][i], data[k - 1][i + (1 << k - 1)]);
            }
        }
    }

    int get_min(int l, int r) {
        int k = std::bit_width<uint32_t>(r - l) - 1;
        return std::min(data[k][l], data[k][r - (1 << k)]);
    }
};

using u64 = uint64_t;

struct TreeBitset {
    std::vector<size_t> sz;
    std::vector<std::vector<u64>> data;
    int lg;
    static constexpr int K = 64;

    TreeBitset(int n) {
        for (int n2 = n; n2 > 1;) {
            n2 = (n2 - 1) / K + 1;
            sz.push_back(n2);
        }
        std::reverse(sz.begin(), sz.end());
        lg = sz.size();
        data.resize(lg);
        for (int i = 0; i < lg; i++) {
            data[i].assign(sz[i], 0);
        }
    }

    void update(int i, int val) {
        for (int k = lg - 1; k >= 0; k--) {
            auto [pos, ind] = div(i, K);
            val = bool(data[k][pos] = (data[k][pos] & (~(1ULL << ind))) | u64(val) << ind);
            i /= K;
        }
    }

    int find_next(int i) {
        int k = lg - 1;
        while (k >= 0) {
            auto [pos, ind] = div(i, K);
            int ind2 = std::countr_zero(data[k][pos] >> ind + 1 << ind + 1);
            if (ind2 != K) {
                i = pos * K + ind2;
                for (k++; k < lg; k++) {
                    i = i * K + std::countr_zero(data[k][i]);
                }
                return i;
            }
            k--, i /= K;
        }
        if (data[lg - 1][0] & 1) {
            return 0;
        }
        return find_next(0);
    }

    int find_prev(int i) {
        int k = lg - 1;
        while (k >= 0) {
            auto [pos, ind] = div(i, K);
            int ind2 = 63 - std::countl_zero(data[k][pos] << (K - ind) >> (K - ind));
            if (ind2 != -1) {
                i = pos * K + ind2;
                for (k++; k < lg; k++) {
                    i = i * K + (63 - std::countl_zero(data[k][i]));
                }
                return i;
            }
            k--, i /= K;
        }
        if (data[lg - 1][sz[lg - 1] - 1] & u64(1) << K - 1) {
            return sz[lg - 1] * K - 1;
        }
        return find_prev(sz[lg - 1] * K - 1);
    }
};

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> gr(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    std::vector<int> input(m);
    for (auto& i : input) {
        std::cin >> i;
        i--;
    }

    std::vector<std::array<int, 3>> quer(q);
    for (int i = 0; i < q; i++) {
        auto& [l, r, id] = quer[i];
        std::cin >> l >> r;
        l--;
        id = i;
    }

    std::vector<int> eul_dp, tin(n), tout(n), depth(n);
    auto dfs = [&](auto dfs, int v, int f) -> void {
        tin[v] = eul_dp.size();
        eul_dp.push_back(depth[v]);
        for (int t : gr[v]) {
            if (t != f) {
                depth[t] = depth[v] + 1;
                dfs(dfs, t, v);
                eul_dp.push_back(depth[v]);
            }
        }
        tout[v] = eul_dp.size();
    };
    dfs(dfs, 0, -1);

    ST st(eul_dp);

    auto get_lca_depth = [&](int u, int v) {
        return st.get_min(std::min(tin[u], tin[v]), std::max(tin[u], tin[v]) + 1);
    };
    auto get_dist = [&](int u, int v) {
        return depth[u] + depth[v] - 2 * get_lca_depth(u, v);
    };
    auto get_dist_tin = [&](int u, int v) {
        return eul_dp[u] + eul_dp[v] - 2 * st.get_min(std::min(u, v), std::max(u, v) + 1);
    };

    constexpr int K = 330;
    std::sort(quer.begin(), quer.end(), [&](auto a, auto b) {
        auto [l1, r1, id1] = a;
        auto [l2, r2, id2] = b;
        if (l1 / K != l2 / K) {
            return l1 / K < l2 / K;
        }
        return (r1 < r2) != bool(l1 / K % 2);
    });

    std::vector<int> ord(m);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int a, int b) { return tin[input[a]] < tin[input[b]]; });
    std::vector<int> pos(m);
    std::vector<int> ord_tin(m);
    for (int i = 0; i < m; i++) {
        pos[ord[i]] = i;
        ord_tin[i] = tin[input[ord[i]]];
    }

    TreeBitset tb(m);

    int64_t total_dlt = 0;
    int sum_dist = 0;
    auto add = [&](int t, int f) {
        total_dlt++;

        // auto it = set.insert(t);
        if (f == 1) {
            tb.update(t, 1);
        }
        int t1 = tb.find_prev(t);
        int t2 = tb.find_next(t);
        if (f == -1) {
            tb.update(t, 0);
        }
        sum_dist -= get_dist_tin(ord_tin[t1], ord_tin[t2]) * f;
        sum_dist += get_dist_tin(ord_tin[t1], ord_tin[t]) * f;
        sum_dist += get_dist_tin(ord_tin[t], ord_tin[t2]) * f;
    };
    int L = 0, R = 0;
    std::vector<int> ans(q);
    for (auto [l, r, id] : quer) {
        while (R < r) {
            add(pos[R++], 1);
        }
        while (l < L) {
            add(pos[--L], 1);
        }
        while (r < R) {
            add(pos[--R], -1);
        }
        while (L < l) {
            add(pos[L++], -1);
        }

        assert(total_dlt <= 1e8);
        ans[id] = sum_dist / 2 + 1;
    }

    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3644kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

67
103
115
98
115
138
83
29
132
127
75
103
88
101
25
118
86
65
78
54
113
130
66
38
9
40
92
115
64
124
46
136
73
62
98
81
119
90
25
100
133
69
90
127
83
133
129
89
34
61
104
126
63
61
104
112
27
74
133
53
80
140
67
100
27
125
110
117
41
89
130
118
136
18
34
118
139
36
103
70
127
115
0
110
138
78
110
...

result:

wrong answer 2nd numbers differ - expected: '97', found: '103'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

score: 0
Wrong Answer
time: 871ms
memory: 25424kb

input:

55321 88650 75523
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

160182
78738
131085
138488
80632
124275
141531
157711
138754
78539
154775
165041
69583
71802
76419
79067
74974
155418
160432
100980
99926
73516
142532
69931
165264
81022
160501
70402
73783
77102
71940
155030
80661
70112
143962
71891
142419
71483
81640
152234
140764
157409
136797
69673
95273
163849
7...

result:

wrong answer 1st numbers differ - expected: '55319', found: '160182'

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 30ms
memory: 14968kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

272
215
181
194
269
234
227
248
175
227
205
209
224
210
218
209
178
241
198
228
273
220
192
227
240
179
235
148
228
166
115
154
181
185
156
150
178
186
148
193
216
220
220
312
159
140
150
119
176
191
96
159
105
122
176
173
166
127
117
172
188
124
119
92
170
178
172
264
195
176
174
187
219
218
169
16...

result:

wrong answer 1st numbers differ - expected: '276', found: '272'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 1070ms
memory: 17224kb

input:

55965 89652 95687
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

44299
7907
41206
18694
49340
45535
2644
30180
18548
17178
46108
49598
33367
46333
33618
31312
47519
47722
49281
45262
31851
19852
14275
36012
51233
21627
45103
33658
20590
36866
47027
12162
44084
17624
24049
46510
43343
41016
35875
42365
33354
35883
42460
25347
12155
19063
30547
39635
43949
43693
31...

result:

wrong answer 1st numbers differ - expected: '42788', found: '44299'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%