| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1031513 |
2024-07-22T23:00:40 Z |
Wael |
Tourism (JOI23_tourism) |
C++14 |
|
0 ms |
0 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> dep(n), sz(n);
function<void(int, int)> calc = [&](int u, int p) {
for (int i = 0; i < adj[u].size(); ++i) {
if (adj[u][i] == p) {
swap(adj[u][i], adj[u].back());
adj[u].pop_back();
break;
}
}
sz[u] = 1;
for (auto v : adj[u]) {
dep[v] = dep[u] + 1;
calc(v, u);
sz[u] += sz[v];
}
for (int i = 1; i < adj[u].size(); ++i) {
if (sz[adj[u][i]] > sz[adj[u][0]]) {
swap(adj[u][i], adj[u][0]);
}
}
};
calc(0, -1);
vector<set<array<int, 4>>> st(n);
vector<vector<pair<int, int>>> update(m);
auto addRange = [&](int l, int r, int v) {
if (l > r) return;
update[l].push_back({l, v});
if (r + 1 < m) {
update[r + 1].push_back({l, -v});
}
};
int const inf = 1e9;
auto append = [&](int u, int l, int r) {
auto it = prev(st[u].upper_bound(array{l, inf, inf, inf}));
auto [L, R, d, t] = *it;
addRange(L, R, d - dep[u]);
if (L == l && r == R && l > 0 && r + 1 < m) {
auto itL = prev(it);
auto itR = next(it);
addRange((*itL)[0], (*itL)[1], (*itL)[2] - dep[u] + 1);
addRange((*itR)[0], (*itR)[1], (*itR)[2] - dep[u] + 1);
int nl = (*itL)[0], nr = (*itR)[1];
st[u].erase(it);
st[u].erase(itL);
st[u].erase(itR);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
} else if (L == l && l > 0) {
auto itL = prev(it);
auto [cl, cr, cd, ct] = *itL;
addRange(cl, cr, cd - dep[u] + 1);
int nl = cl, nr = r;
st[u].erase(it);
st[u].erase(itL);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
if (r < R) {
st[u].insert(array{r + 1, R, dep[u], 0});
}
} else if (r == R && r + 1 < m) {
auto itR = next(it);
auto [cl, cr, cd, ct] = *itR;
addRange(cl, cr, cd - dep[u] + 1);
int nl = l, nr = cr;
st[u].erase(it);
st[u].erase(itR);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
if (L < l) {
st[u].insert(array{L, l - 1, dep[u], 0});
}
} else {
st[u].erase(it);
st[u].insert(array{l, r, dep[u] - 1, 1});
if (L < l) {
st[u].insert(array{L, l - 1, dep[u], 0});
}
if (r < R) {
st[u].insert(array{r + 1, R, dep[u], 0});
}
}
};
function<void(int)> dfs = [&](int u) {
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
dfs(v);
if (i == 0) {
swap(st[u], st[v]);
} else {
for (auto [l, r, d, t] : st[v]) {
if (t == 1) {
addRange(l, r, d - dep[u] + 1);
append(u, l, r);
} else {
addRange(l, r, d - dep[v] + 1);
}
}
set<array<int, 4>>().swap(st[v]);
}
}
if (st[u].size() == 0) {
st[u] = {{0, m - 1, dep[u], 0}};
}
for (auto i : indices[u]) {
append(u, i, i);
}
};
dfs(0);
for (auto [l, r, d, t] : st[0]) {
addRange(l, r, d - dep[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:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
tourism.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 1; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
tourism.cpp: In lambda function:
tourism.cpp:105:47: error: missing template arguments before '{' token
105 | auto it = prev(st[u].upper_bound(array{l, inf, inf, inf}));
| ^
tourism.cpp:106:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
106 | auto [L, R, d, t] = *it;
| ^
tourism.cpp:117:31: error: missing template arguments before '{' token
117 | st[u].insert(array{nl, nr, dep[u] - 1, 1});
| ^
tourism.cpp:113:17: warning: unused variable 'nl' [-Wunused-variable]
113 | int nl = (*itL)[0], nr = (*itR)[1];
| ^~
tourism.cpp:120:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | auto [cl, cr, cd, ct] = *itL;
| ^
tourism.cpp:125:31: error: missing template arguments before '{' token
125 | st[u].insert(array{nl, nr, dep[u] - 1, 1});
| ^
tourism.cpp:127:35: error: missing template arguments before '{' token
127 | st[u].insert(array{r + 1, R, dep[u], 0});
| ^
tourism.cpp:122:17: warning: unused variable 'nl' [-Wunused-variable]
122 | int nl = cl, nr = r;
| ^~
tourism.cpp:122:26: warning: unused variable 'nr' [-Wunused-variable]
122 | int nl = cl, nr = r;
| ^~
tourism.cpp:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | auto [cl, cr, cd, ct] = *itR;
| ^
tourism.cpp:136:31: error: missing template arguments before '{' token
136 | st[u].insert(array{nl, nr, dep[u] - 1, 1});
| ^
tourism.cpp:138:35: error: missing template arguments before '{' token
138 | st[u].insert(array{L, l - 1, dep[u], 0});
| ^
tourism.cpp:133:17: warning: unused variable 'nl' [-Wunused-variable]
133 | int nl = l, nr = cr;
| ^~
tourism.cpp:133:25: warning: unused variable 'nr' [-Wunused-variable]
133 | int nl = l, nr = cr;
| ^~
tourism.cpp:142:31: error: missing template arguments before '{' token
142 | st[u].insert(array{l, r, dep[u] - 1, 1});
| ^
tourism.cpp:144:35: error: missing template arguments before '{' token
144 | st[u].insert(array{L, l - 1, dep[u], 0});
| ^
tourism.cpp:147:35: error: missing template arguments before '{' token
147 | st[u].insert(array{r + 1, R, dep[u], 0});
| ^
tourism.cpp: In lambda function:
tourism.cpp:153:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int i = 0; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
tourism.cpp:159:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
159 | for (auto [l, r, d, t] : st[v]) {
| ^
tourism.cpp: In function 'void solve()':
tourism.cpp:178:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
178 | for (auto [l, r, d, t] : st[0]) {
| ^
tourism.cpp:190:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
190 | for (auto [j, v] : update[i]) {
| ^
tourism.cpp:103:15: warning: unused variable 'inf' [-Wunused-variable]
103 | int const inf = 1e9;
| ^~~
