| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1031293 |
2024-07-22T17:01:26 Z |
Wael |
Tourism (JOI23_tourism) |
C++17 |
|
2177 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct SegmentTree {
int n;
vector<int> sum;
SegmentTree(int n) : n(n) {
sum.assign(4 * n, 0);
}
void update(int i, int v) {
update(i, v, 0, 0, n - 1);
}
void update(int i, int v, int x, int lx, int rx) {
if (lx == rx) {
sum[x] += v;
return;
}
int mid = (lx + rx) / 2;
if (i <= mid) {
update(i, v, 2 * x + 1, lx, mid);
} else {
update(i, v, 2 * x + 2, mid + 1, rx);
}
sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
}
int get(int l, int r) {
return get(l, r, 0, 0, n - 1);
}
int get(int l, int r, int x, int lx, int rx) {
if (lx > r || rx < l) return 0;
if (l <= lx && rx <= r) return sum[x];
int mid = (lx + rx) / 2;
return get(l, r, 2 * x + 1, lx, mid) + get(l, r, 2 * x + 2, mid + 1, rx);
}
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> c(m);
vector<vector<int>> indices(n);
for (int i = 0; i < m; ++i) {
cin >> c[i];
--c[i];
indices[c[i]].push_back(i);
}
vector<int> l(q), r(q);
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
--l[i], --r[i];
}
vector<int> belong(m);
vector<vector<int>> st(n);
vector<vector<pair<int, int>>> update(m);
auto addRange = [&](int l, int r) {
if (l > r) return;
update[l].push_back({l, 1});
if (r + 1 < m) {
update[r + 1].push_back({l, -1});
}
};
function<void(int, int)> dfs = [&](int u, int p) {
for (auto v : adj[u]) {
if (v == p) continue;
dfs(v, u);
for (auto i : st[v]) {
st[u].push_back(i);
}
}
for (auto i : indices[u]) {
st[u].push_back(i);
belong[i] = u;
}
sort(st[u].begin(), st[u].end());
if (st[u].size()) {
addRange(0, st[u][0] - 1);
} else {
addRange(0, m - 1);
}
for (int i = 0; i < st[u].size(); ++i) {
if ((i + 1 < st[u].size() && st[u][i + 1] != st[u][i] + 1) || (i + 1 == st[u].size())) {
int next = (i + 1 < st[u].size() ? st[u][i + 1] - 1 : m - 1);
addRange(st[u][i] + 1, next);
}
if (belong[st[u][i]] == u) continue;
int j = i;
while (j + 1 < st[u].size() && st[u][j] + 1 == st[u][j + 1] && belong[st[u][j]] == belong[st[u][j + 1]]) {
++j;
}
addRange(st[u][i], st[u][j]);
i = j;
}
for (auto i : st[u]) {
belong[i] = u;
}
};
dfs(0, -1);
vector<vector<int>> query(m);
for (int i = 0; i < q; ++i) {
query[r[i]].push_back(i);
}
vector<int> ans(q);
SegmentTree seg(m);
for (int i = 0; i < m; ++i) {
for (auto [j, v] : update[i]) {
seg.update(j, v);
}
for (auto j : query[i]) {
ans[j] = n - seg.get(0, l[j]);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Compilation message
tourism.cpp: In lambda function:
tourism.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < st[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~
tourism.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if ((i + 1 < st[u].size() && st[u][i + 1] != st[u][i] + 1) || (i + 1 == st[u].size())) {
| ~~~~~~^~~~~~~~~~~~~~
tourism.cpp:99:82: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if ((i + 1 < st[u].size() && st[u][i + 1] != st[u][i] + 1) || (i + 1 == st[u].size())) {
| ~~~~~~^~~~~~~~~~~~~~~
tourism.cpp:100:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | int next = (i + 1 < st[u].size() ? st[u][i + 1] - 1 : m - 1);
| ~~~~~~^~~~~~~~~~~~~~
tourism.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while (j + 1 < st[u].size() && st[u][j] + 1 == st[u][j + 1] && belong[st[u][j]] == belong[st[u][j + 1]]) {
| ~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
464 KB |
Output is correct |
| 4 |
Runtime error |
2177 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
217 ms |
43744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
540 ms |
74140 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
