| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 950888 |
2024-03-20T22:19:52 Z |
vjudge1 |
Tourism (JOI23_tourism) |
C++17 |
|
608 ms |
20464 KB |
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double; // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
struct AIB {
int n;
vi V;
AIB(int N) : n(N + 1), V(N + 1) {}
void update(int p, int v) {
++p;
while(p < n) {
V[p] += v;
p += p & - p;
}
}
int query(int p) {
++p;
int re = 0;
while(p) {
re += V[p];
p -= p & -p;
}
return re;
}
int query(int st, int dr) {
return query(dr) - query(st - 1);
}
};
struct Segmente {
int n;
set<pair<ii, int> > S;
AIB Fr;
Segmente(int N) : n(N), Fr(N + 1) {
S.insert({ii{0, n - 1}, n + 1});
Fr.update(n + 1, n);
}
void init() {
}
void update(int l, int r, int v) { /// l...r <- v
if(l > r) return;
auto primul = S.upper_bound({ii{l, 1e9}, 0});
--primul;
auto ultimul = S.lower_bound({ii{r + 1, -1e9}, 0});
--ultimul;
vector<pair<ii, int> > ToDelete;
while(primul != ultimul) {
ToDelete.push_back(*primul);
++primul;
}
ToDelete.push_back(*primul);
auto sterge = [&](pair<ii, int> a) {
S.erase(a);
auto [st, dr] = a.first;
int len = dr - st + 1;
Fr.update(a.second, -len);
};
auto adauga = [&](int st, int dr, int v) {
pair<ii, int> a = {ii{st, dr}, v};
S.insert(a);
int len = dr - st + 1;
Fr.update(v, len);
};
for(auto it : ToDelete) sterge(it);
auto minus = [&](ii seg1, ii seg2) -> vector<ii> {
auto [s1, d1] = seg1;
auto [s2, d2] = seg2;
if(d1 < s2 || d2 < s1) return {seg1};
// if(s2 <= s1 && d1 <= d2) return {};
// if(s1 < s2 && d1 <= d2) return {ii{s1, s2 - 1}};
// if(s2 <= s1 && d2 < d1) return {ii{d2 + 1, d1}};
return {ii{s1, s2 - 1}, ii{d2 + 1, d1}};
};
auto len = [&](ii a) { return a.second - a.first + 1; };
auto scrap = [&](auto x) {
for(auto it : minus(x.first, ii{l, r}))
if(len(it) > 0) adauga(it.first, it.second, x.second);
};
scrap(ToDelete[0]);
if(ToDelete.size() > 1) scrap(ToDelete.back());
adauga(l, r, v);
}
int query(int r) {
return Fr.query(r);
}
};
struct tree {
int n, tmr = 0;
vi par, niv, sz, nxt, in;
vector<vi> L, G, Anc;
Segmente A;
tree(int N) : n(N), par(N), niv(N), sz(N, 0),
nxt(N, 0), in(N, 0), L(N), G(N), A(N) {} /// nxt[u] e capul la lant
void add_edge(int u, int v) {
L[u].push_back(v);
L[v].push_back(u);
}
void init() {
function<void(int, int, int)> dfs0 = [&](int u, int p, int li) {
par[u] = p;
niv[u] = li;
sz[u] = 1;
for (auto it : L[u])
if (it != p) {
dfs0(it, u, li + 1);
sz[u] += it;
G[u].push_back(it);
}
};
dfs0(0, -1, 0);
A.init();
function<void(int, int)> dfs1 = [&](int u, int p) {
sort(all(G[u]), [&](auto a, auto b) { return sz[a] > sz[b]; });
in[u] = tmr++;
if (G[u].empty()) return;
nxt[G[u][0]] = nxt[u];
dfs1(G[u][0], u);
for (int i = 1; i < G[u].size(); ++i) {
nxt[G[u][i]] = G[u][i];
dfs1(G[u][i], u);
}
};
dfs1(0, -1);
Anc.push_back(par);
for (int k = 1; (1 << k) <= n; ++k) {
Anc.push_back(vi(n, -1));
for (int i = 0; i < n; ++i) {
Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]];
}
}
}
int lift(int u, int nr) {
for (int i = 0; i < (int)Anc.size(); ++i)
if (nr & (1 << i))
u = Anc[i][u];
return u;
}
int lca(int u, int v) {
if(niv[u] > niv[v]) swap(u, v);
v = lift(v, niv[v] - niv[u]);
if(u == v) return u;
for(int i = (int)Anc.size() - 1; i >= 0; --i)
if(Anc[i][u] != Anc[i][v]) {
u = Anc[i][u];
v = Anc[i][v];
}
return par[u];
}
void update_lant(int l, int u, int val) { /// (l, u] update
if(niv[l] == niv[u]) return;
while(u != -1) {
if(niv[nxt[u]] > niv[l]) {
A.update(in[nxt[u]], in[u], val);
u = par[nxt[u]];
} else {
A.update(in[l] + 1, in[u], val);
break;
}
}
}
void update(int u, int v, int val) {
int l = lca(u, v);
update_lant(l, u, val);
update_lant(l, v, val);
}
int query(int r) { /// nr chestii <= r
return A.query(r);
}
};
struct RMQ_LCA {
int m;
tree &T;
vi C;
vector<vi> Re;
RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
Re.push_back(C);
for(int k = 1; (1 << k) <= m; ++k) {
Re.push_back(vi(m, 0));
for(int i = 0; i < m; ++i) {
if(i + (1 << (k - 1)) < m)
Re[k][i] = T.lca(Re[k - 1][i], Re[k - 1][i + (1 << (k - 1))]);
else Re[k][i] = Re[k - 1][i];
}
}
}
int query(int st, int dr) {
int l = 31 - __builtin_clz(dr - st + 1);
return T.lca(Re[l][st], Re[l][dr - (1 << l) + 1]);
}
};
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, m, q;
cin >> n >> m >> q;
tree T(n);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
T.add_edge(u, v);
}
T.init();
vi C(m);
for(int i = 0; i < m; ++i) {
cin >> C[i];
--C[i];
}
RMQ_LCA Stramos(n, C, T);
int rad = (int)round(sqrt(double(n)));
vector<pair<ii, int> > Q;
vi Re(q, 0);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l; --r;
Q.push_back({ii{l, r}, i});
}
sort(all(Q));
int ult = C.back();
int p = int(Q.size()) - 1;
for(int i = m - 1; i >= 0; --i) {
T.update(ult, C[i], i + 1);
ult = C[i];
while(p >= 0 && Q[p].first.first == i) {
auto [seg, id] = Q[p];
auto [l, r] = seg;
Re[id] = T.query(r);
--p;
}
}
for(auto it : Re)
cout << it + 1 << "\n";
return 0;
}
Compilation message
tourism.cpp: In lambda function:
tourism.cpp:152:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 1; i < G[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
tourism.cpp: In constructor 'RMQ_LCA::RMQ_LCA(int, vi, tree&)':
tourism.cpp:214:8: warning: 'RMQ_LCA::C' will be initialized after [-Wreorder]
214 | vi C;
| ^
tourism.cpp:213:11: warning: 'tree& RMQ_LCA::T' [-Wreorder]
213 | tree &T;
| ^
tourism.cpp:217:5: warning: when initialized here [-Wreorder]
217 | RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
| ^~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:256:9: warning: unused variable 'rad' [-Wunused-variable]
256 | int rad = (int)round(sqrt(double(n)));
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
366 ms |
16852 KB |
Output is correct |
| 3 |
Incorrect |
608 ms |
20464 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
