# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
812726 |
2023-08-07T10:29:43 Z |
hugo_pm |
Tourism (JOI23_tourism) |
C++17 |
|
5000 ms |
26980 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))
template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }
using pii = pair<int, int>;
using vi = vector<int>;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const int LG = 17;
static_assert((1<<LG) > 100'000);
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int nbNode, nbSpot, nbReq;
cin >> nbNode >> nbSpot >> nbReq;
vector<vi> adj(nbNode);
rep(iEdge, 0, nbNode-1) {
int u, v; cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vi> anc(LG, vi(nbNode, -1));
vector<int> tin(nbNode), tout(nbNode), prof(nbNode);
{
int lastTime = 0;
auto Dfs = [&] (auto dfs, int node, int parent) -> void {
anc[0][node] = parent;
rep(lvl, 0, LG-1) {
if (anc[lvl][node] == -1) break;
anc[lvl+1][node] = anc[lvl][anc[lvl][node]];
}
tin[node] = lastTime++;
for (int child : adj[node]) if (child != parent) {
prof[child] = prof[node]+1;
dfs(dfs, child, node);
}
tout[node] = lastTime++;
};
Dfs(Dfs, 0, -1);
}
auto ancestor = [&] (int ance, int child) {
return tin[ance] <= tin[child] && tout[child] <= tout[ance];
};
auto lca = [&] (int u, int v) {
if (prof[u] > prof[v]) swap(u, v);
int firstJmp = prof[v] - prof[u];
rep(lvl, 0, LG) if ((1<<lvl) & firstJmp) {
v = anc[lvl][v];
}
assert(prof[u] == prof[v]);
if (u == v) return u;
for (int lvl = LG-1; lvl >= 0; --lvl) {
int pu = anc[lvl][u], pv = anc[lvl][v];
if (pu != -1 && pv != -1 && pu != pv) {
u = pu, v = pv;
}
}
assert(u != v);
u = anc[0][u], v = anc[0][v];
assert(u == v);
return u;
};
vector<int> spots(nbSpot);
rep(iSpot, 0, nbSpot) {
cin >> spots[iSpot];
--spots[iSpot];
}
rep(iReq, 0, nbReq) {
int L, R;
cin >> L >> R;
--L, --R;
int ans = 0;
vector<int> itv(begin(spots)+L, begin(spots)+R+1);
sort(all(itv), [&] (int i, int j) { return tin[i] < tin[j]; });
rep(i, 0, R-L) { // attention!
itv.push_back(lca(itv[i], itv[i+1]));
}
sort(all(itv), [&] (int i, int j) { return tin[i] < tin[j]; });
int szItv = sz(itv);
auto Virt = [&] (auto virt, int iCur) -> int {
int iLook = iCur+1;
while (iLook < szItv && ancestor(itv[iCur], itv[iLook])) {
ans += prof[itv[iLook]] - prof[itv[iCur]];
iLook = virt(virt, iLook);
}
return iLook;
};
assert(Virt(Virt, 0) == szItv);
cout << ans+1 << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
272 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
324 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
5 ms |
340 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
12 ms |
392 KB |
Output is correct |
13 |
Correct |
12 ms |
340 KB |
Output is correct |
14 |
Correct |
12 ms |
396 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
5 ms |
340 KB |
Output is correct |
17 |
Correct |
4 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
340 KB |
Output is correct |
19 |
Correct |
6 ms |
340 KB |
Output is correct |
20 |
Correct |
4 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
340 KB |
Output is correct |
22 |
Correct |
6 ms |
340 KB |
Output is correct |
23 |
Correct |
4 ms |
436 KB |
Output is correct |
24 |
Correct |
4 ms |
340 KB |
Output is correct |
25 |
Correct |
5 ms |
340 KB |
Output is correct |
26 |
Correct |
4 ms |
432 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
272 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
324 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
5 ms |
340 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
12 ms |
392 KB |
Output is correct |
13 |
Correct |
12 ms |
340 KB |
Output is correct |
14 |
Correct |
12 ms |
396 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
5 ms |
340 KB |
Output is correct |
17 |
Correct |
4 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
340 KB |
Output is correct |
19 |
Correct |
6 ms |
340 KB |
Output is correct |
20 |
Correct |
4 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
340 KB |
Output is correct |
22 |
Correct |
6 ms |
340 KB |
Output is correct |
23 |
Correct |
4 ms |
436 KB |
Output is correct |
24 |
Correct |
4 ms |
340 KB |
Output is correct |
25 |
Correct |
5 ms |
340 KB |
Output is correct |
26 |
Correct |
4 ms |
432 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
111 ms |
704 KB |
Output is correct |
31 |
Correct |
164 ms |
700 KB |
Output is correct |
32 |
Correct |
240 ms |
828 KB |
Output is correct |
33 |
Correct |
259 ms |
832 KB |
Output is correct |
34 |
Correct |
248 ms |
820 KB |
Output is correct |
35 |
Correct |
764 ms |
800 KB |
Output is correct |
36 |
Correct |
762 ms |
812 KB |
Output is correct |
37 |
Correct |
772 ms |
800 KB |
Output is correct |
38 |
Correct |
213 ms |
900 KB |
Output is correct |
39 |
Correct |
238 ms |
1024 KB |
Output is correct |
40 |
Correct |
220 ms |
908 KB |
Output is correct |
41 |
Correct |
742 ms |
904 KB |
Output is correct |
42 |
Correct |
683 ms |
908 KB |
Output is correct |
43 |
Correct |
716 ms |
876 KB |
Output is correct |
44 |
Correct |
206 ms |
852 KB |
Output is correct |
45 |
Correct |
222 ms |
844 KB |
Output is correct |
46 |
Correct |
208 ms |
864 KB |
Output is correct |
47 |
Correct |
690 ms |
832 KB |
Output is correct |
48 |
Correct |
765 ms |
812 KB |
Output is correct |
49 |
Correct |
682 ms |
828 KB |
Output is correct |
50 |
Correct |
176 ms |
864 KB |
Output is correct |
51 |
Correct |
188 ms |
864 KB |
Output is correct |
52 |
Correct |
195 ms |
864 KB |
Output is correct |
53 |
Correct |
247 ms |
848 KB |
Output is correct |
54 |
Correct |
180 ms |
980 KB |
Output is correct |
55 |
Correct |
191 ms |
868 KB |
Output is correct |
56 |
Correct |
60 ms |
492 KB |
Output is correct |
57 |
Correct |
1 ms |
724 KB |
Output is correct |
58 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
57 ms |
468 KB |
Output is correct |
4 |
Execution timed out |
5062 ms |
22100 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
45 ms |
13576 KB |
Output is correct |
3 |
Correct |
75 ms |
15160 KB |
Output is correct |
4 |
Correct |
53 ms |
16812 KB |
Output is correct |
5 |
Correct |
94 ms |
26980 KB |
Output is correct |
6 |
Correct |
133 ms |
25412 KB |
Output is correct |
7 |
Correct |
159 ms |
24776 KB |
Output is correct |
8 |
Correct |
115 ms |
24660 KB |
Output is correct |
9 |
Correct |
106 ms |
24524 KB |
Output is correct |
10 |
Correct |
105 ms |
24580 KB |
Output is correct |
11 |
Correct |
99 ms |
24672 KB |
Output is correct |
12 |
Correct |
134 ms |
24584 KB |
Output is correct |
13 |
Correct |
109 ms |
24656 KB |
Output is correct |
14 |
Correct |
86 ms |
24976 KB |
Output is correct |
15 |
Correct |
76 ms |
25944 KB |
Output is correct |
16 |
Correct |
118 ms |
25708 KB |
Output is correct |
17 |
Correct |
122 ms |
25824 KB |
Output is correct |
18 |
Correct |
95 ms |
25832 KB |
Output is correct |
19 |
Correct |
108 ms |
26424 KB |
Output is correct |
20 |
Correct |
96 ms |
25324 KB |
Output is correct |
21 |
Correct |
104 ms |
24600 KB |
Output is correct |
22 |
Correct |
105 ms |
24324 KB |
Output is correct |
23 |
Correct |
88 ms |
24136 KB |
Output is correct |
24 |
Correct |
133 ms |
24148 KB |
Output is correct |
25 |
Correct |
132 ms |
24152 KB |
Output is correct |
26 |
Correct |
132 ms |
24320 KB |
Output is correct |
27 |
Correct |
122 ms |
24160 KB |
Output is correct |
28 |
Correct |
141 ms |
24140 KB |
Output is correct |
29 |
Correct |
145 ms |
24192 KB |
Output is correct |
30 |
Correct |
131 ms |
24244 KB |
Output is correct |
31 |
Correct |
146 ms |
24304 KB |
Output is correct |
32 |
Correct |
103 ms |
24448 KB |
Output is correct |
33 |
Correct |
121 ms |
24772 KB |
Output is correct |
34 |
Correct |
75 ms |
25528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
58 ms |
508 KB |
Output is correct |
4 |
Execution timed out |
5007 ms |
17540 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
272 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
324 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
5 ms |
340 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
12 ms |
392 KB |
Output is correct |
13 |
Correct |
12 ms |
340 KB |
Output is correct |
14 |
Correct |
12 ms |
396 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
5 ms |
340 KB |
Output is correct |
17 |
Correct |
4 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
340 KB |
Output is correct |
19 |
Correct |
6 ms |
340 KB |
Output is correct |
20 |
Correct |
4 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
340 KB |
Output is correct |
22 |
Correct |
6 ms |
340 KB |
Output is correct |
23 |
Correct |
4 ms |
436 KB |
Output is correct |
24 |
Correct |
4 ms |
340 KB |
Output is correct |
25 |
Correct |
5 ms |
340 KB |
Output is correct |
26 |
Correct |
4 ms |
432 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
111 ms |
704 KB |
Output is correct |
31 |
Correct |
164 ms |
700 KB |
Output is correct |
32 |
Correct |
240 ms |
828 KB |
Output is correct |
33 |
Correct |
259 ms |
832 KB |
Output is correct |
34 |
Correct |
248 ms |
820 KB |
Output is correct |
35 |
Correct |
764 ms |
800 KB |
Output is correct |
36 |
Correct |
762 ms |
812 KB |
Output is correct |
37 |
Correct |
772 ms |
800 KB |
Output is correct |
38 |
Correct |
213 ms |
900 KB |
Output is correct |
39 |
Correct |
238 ms |
1024 KB |
Output is correct |
40 |
Correct |
220 ms |
908 KB |
Output is correct |
41 |
Correct |
742 ms |
904 KB |
Output is correct |
42 |
Correct |
683 ms |
908 KB |
Output is correct |
43 |
Correct |
716 ms |
876 KB |
Output is correct |
44 |
Correct |
206 ms |
852 KB |
Output is correct |
45 |
Correct |
222 ms |
844 KB |
Output is correct |
46 |
Correct |
208 ms |
864 KB |
Output is correct |
47 |
Correct |
690 ms |
832 KB |
Output is correct |
48 |
Correct |
765 ms |
812 KB |
Output is correct |
49 |
Correct |
682 ms |
828 KB |
Output is correct |
50 |
Correct |
176 ms |
864 KB |
Output is correct |
51 |
Correct |
188 ms |
864 KB |
Output is correct |
52 |
Correct |
195 ms |
864 KB |
Output is correct |
53 |
Correct |
247 ms |
848 KB |
Output is correct |
54 |
Correct |
180 ms |
980 KB |
Output is correct |
55 |
Correct |
191 ms |
868 KB |
Output is correct |
56 |
Correct |
60 ms |
492 KB |
Output is correct |
57 |
Correct |
1 ms |
724 KB |
Output is correct |
58 |
Correct |
1 ms |
724 KB |
Output is correct |
59 |
Correct |
1 ms |
212 KB |
Output is correct |
60 |
Correct |
2 ms |
340 KB |
Output is correct |
61 |
Correct |
57 ms |
468 KB |
Output is correct |
62 |
Execution timed out |
5062 ms |
22100 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |