QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525955 | #6340. Tourism | Qwerty1232 | 0 | 1070ms | 25424kb | C++23 | 5.8kb | 2024-08-21 05:19:00 | 2024-08-21 05:19:03 |
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)]);
}
};
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%