QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525962 | #6340. Tourism | Qwerty1232 | 0 | 1271ms | 25500kb | C++23 | 5.9kb | 2024-08-21 05:28:29 | 2024-08-21 05:28:31 |
Judging History
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%