QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525962#6340. TourismQwerty12320 1271ms25500kbC++235.9kb2024-08-21 05:28:292024-08-21 05:28:31

Judging History

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

  • [2024-08-21 05:28:31]
  • 评测
  • 测评结果:0
  • 用时:1271ms
  • 内存:25500kb
  • [2024-08-21 05:28:29]
  • 提交

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)]);
    }
};

struct TreeBitset {
    using T = uint32_t;
    static constexpr int K = sizeof(T) * 8;
    std::vector<size_t> sz;
    std::vector<std::vector<T>> data;
    int lg;

    TreeBitset(int n) {
        if (n == 1) {
            sz = {1};
        }
        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] & (~(T(1) << ind))) | T(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<T>(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<T>(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 = (K - 1) - std::countl_zero<T>(T(data[k][pos] << (K - ind)) >> (K - ind));
            if (ind2 != -1) {
                i = pos * K + ind2;
                for (k++; k < lg; k++) {
                    i = i * K + ((K - 1) - std::countl_zero<T>(data[k][i]));
                }
                return i;
            }
            k--, i /= K;
        }
        if (data[lg - 1][sz[lg - 1] - 1] & T(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: 3656kb

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
107
119
98
119
146
94
25
135
134
76
110
91
101
25
122
86
65
86
54
120
144
66
38
6
48
95
119
62
131
46
143
73
70
101
85
122
90
22
104
140
69
93
130
81
136
136
96
34
69
108
130
63
59
107
119
26
74
140
51
78
147
68
107
30
129
114
124
41
93
133
121
143
20
30
125
146
44
107
72
131
122
11
114
145
79
11...

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

score: 0
Wrong Answer
time: 1020ms
memory: 25500kb

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:

55688
14269
41026
55574
19106
37365
61026
51893
58377
38268
47438
73459
42454
45225
34505
14806
36847
48070
54523
2647
13103
33879
57116
43175
74465
18912
45811
42397
36816
38474
29427
38689
19179
32201
58042
44297
73523
44560
21094
65803
61989
51286
51487
16580
-7824
73597
38367
36677
15547
25213
2...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 42ms
memory: 14944kb

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:

200
145
111
118
196
137
115
154
99
136
111
139
152
151
143
130
83
153
118
124
169
104
106
147
167
101
166
76
153
109
36
88
130
108
115
109
140
156
113
165
157
139
142
213
64
38
37
10
74
92
-9
65
13
32
36
27
25
9
-14
16
54
-25
3
-24
54
43
54
159
65
63
27
44
54
63
19
19
50
102
70
82
145
75
30
80
27
97...

result:

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

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 1271ms
memory: 17244kb

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:

46126
8076
42645
19120
51629
47430
2383
31227
18650
17068
48293
51761
34705
48588
34962
32348
49672
50133
51481
47535
33007
20236
14403
37295
53571
22140
46854
34481
20665
38338
49444
11896
46117
17491
24885
48782
45122
42936
37273
43795
34710
37203
43913
26114
11998
19097
31794
41383
45250
45415
32...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #1:

0%