#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
const int mn = 1e5 + 10;
int up[mn][17], sight[mn];
vector<int> adj[mn];
pii qry[mn];
int n, m, q;
bool stickTree = 1;
/* subtask */
namespace sub_2 {
int sz[mn], mark[mn];
int szDfs (int u, int p) {
sz[u] = mark[u];
for (int v : adj[u])
if (v != p) sz[u] += szDfs(v, u);
return sz[u];
}
int dfs (int u, int p, bool toParent = 0) {
int child = 0, ans = 0;
for (int v : adj[u])
if (v != p && sz[v]) child++;
toParent |= (child > 1 || mark[u]);
for (int v : adj[u]) {
if (v == p || !sz[v]) continue;
ans += dfs(v, u, toParent);
}
return ans + toParent;
}
void solve() {
for (int j = 0; j < q; j++) {
for (int i = 1; i <= n; i++) mark[i] = 0;
for (int i = qry[j].first; i <= qry[j].second; i++) mark[sight[i]] = 1;
szDfs(1, 1);
cout << dfs(1, 1) << "\n";
}
}
bool check() {
return n <= 2000 && m <= 2000 && q <= 2000;
}
}
/* end of subtask */
/* subtask */
namespace sub_3 {
int max_spt[mn][17], min_spt[mn][17];
int query (int l, int r) {
int p = 31 - __builtin_clz(r - l + 1);
int lo = min(min_spt[l][p], min_spt[r - (1 << p) + 1][p]);
int hi = max(max_spt[l][p], max_spt[r - (1 << p) + 1][p]);
return hi - lo + 1;
}
void solve() {
for (int i = 1; i <= m; i++) max_spt[i][0] = min_spt[i][0] = sight[i];
for (int s = 1; (1 << s) <= m; s++) {
for (int i = 1; i + (1 << s) - 1 <= m; i++) {
int p = s - 1;
max_spt[i][s] = max(max_spt[i][p], max_spt[i + (1 << p)][p]);
min_spt[i][s] = min(min_spt[i][p], min_spt[i + (1 << p)][p]);
}
}
for (int i = 0; i < q; i++) {
int l, r; tie(l, r) = qry[i];
cout << query(l, r) << "\n";
}
}
bool check() {
return stickTree;
}
}
/* end of subtask */
/* subtask */
namespace sub_4 {
int spt[mn][21], up[mn][21], depth[mn], num[mn], sz[mn];
int timeDfs;
int dfs (int u, int p, int d) {
up[u][0] = p, depth[u] = d, num[u] = ++timeDfs, sz[u] = 1;
for (int i = 1; i < 21; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : adj[u])
if (v != p) sz[u] += dfs(v, u, d + 1);
return sz[u];
}
int goUp (int a, int k) {
int LOG = 31 - __builtin_clz(k);
for (int i = 0; i <= LOG; i++)
if (k & (1 << i)) a = up[a][i];
return a;
}
int lca (int a, int b) {
a = goUp(a, max(0, depth[a] - depth[b]));
b = goUp(b, max(0, depth[b] - depth[a]));
if (a == b) return a;
for (int i = 20; i >= 0; i--)
if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
return up[a][0];
}
int dist (int a, int b) {
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
struct BIT {
vector<int> tr;
BIT (int sz) : tr(4 * sz) {}
int p (int k) { return k & -k; }
void update (int k, int val) {
for (; k < tr.size(); k += p(k)) tr[k] += val;
}
int sum (int k, int ans = 0) {
for (; k; k -= p(k)) ans += tr[k];
return ans;
}
int query (int l, int r) { return sum(r) - sum(l - 1); }
};
bool inTree (int subtr, int node) {
return num[subtr] <= num[node] && num[node] < num[subtr] + sz[subtr];
}
int query (int l, int r) {
int p = 31 - __builtin_clz(r - l + 1);
return lca(spt[l][p], spt[r - (1 << p) + 1][p]);
}
void solve() {
dfs(1, 1, 1);
for (int i = 1; i <= m; i++) spt[i][0] = sight[i];
for (int s = 1; (1 << s) <= m; s++) {
for (int i = 1; i + (1 << s) - 1 <= m; i++) {
int p = s - 1;
spt[i][s] = lca(spt[i][p], spt[i + (1 << p)][p]);
}
}
BIT tree(n);
for (int i = 0; i < q; i++) {
int ans = 0, l = qry[i].first;
for (int r = qry[i].first; r <= qry[i].second; r++) {
if (l == r) ans = 1;
else if (inTree(query(l, r - 1), sight[r])) {
int node = sight[r];
for (int i = 20; i >= 0; i--) {
int p = up[node][i];
if (!tree.query(num[p], num[p] + sz[p] - 1)) node = p;
}
ans += depth[sight[r]] - depth[node] + 1;
}
else ans += dist(query(l, r - 1), sight[r]);
tree.update(num[sight[r]], 1);
}
cout << ans << "\n";
}
}
bool check() {
if (qry[0].first != 1 || qry[q - 1].second != m) return 0;
for (int i = 0; i < q - 1; i++)
if (qry[i].second + 1 != qry[i + 1].first) return 0;
return 1;
}
}
/* end of subtask */
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
stickTree &= (a == i && b == i + 1);
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= m; i++) cin >> sight[i];
for (int i = 0; i < q; i++) {
int l, r; cin >> l >> r;
qry[i] = {l, r};
}
if (sub_2::check()) return sub_2::solve(), 0;
if (sub_3::check()) return sub_3::solve(), 0;
if (sub_4::check()) return sub_4::solve(), 0;
return 0;
}
Compilation message
tourism.cpp: In member function 'void sub_4::BIT::update(int, int)':
tourism.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (; k < tr.size(); k += p(k)) tr[k] += val;
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
2 ms |
6492 KB |
Output is correct |
26 |
Correct |
2 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
2 ms |
6492 KB |
Output is correct |
26 |
Correct |
2 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6756 KB |
Output is correct |
30 |
Correct |
34 ms |
6492 KB |
Output is correct |
31 |
Correct |
45 ms |
6492 KB |
Output is correct |
32 |
Correct |
75 ms |
6492 KB |
Output is correct |
33 |
Correct |
74 ms |
6488 KB |
Output is correct |
34 |
Correct |
77 ms |
6492 KB |
Output is correct |
35 |
Correct |
73 ms |
6680 KB |
Output is correct |
36 |
Correct |
77 ms |
6680 KB |
Output is correct |
37 |
Correct |
76 ms |
6668 KB |
Output is correct |
38 |
Correct |
73 ms |
6752 KB |
Output is correct |
39 |
Correct |
75 ms |
6756 KB |
Output is correct |
40 |
Correct |
77 ms |
6744 KB |
Output is correct |
41 |
Correct |
75 ms |
6992 KB |
Output is correct |
42 |
Correct |
75 ms |
6744 KB |
Output is correct |
43 |
Correct |
77 ms |
6744 KB |
Output is correct |
44 |
Correct |
71 ms |
6492 KB |
Output is correct |
45 |
Correct |
76 ms |
6692 KB |
Output is correct |
46 |
Correct |
71 ms |
6492 KB |
Output is correct |
47 |
Correct |
76 ms |
6488 KB |
Output is correct |
48 |
Correct |
75 ms |
6492 KB |
Output is correct |
49 |
Correct |
77 ms |
6744 KB |
Output is correct |
50 |
Correct |
41 ms |
6696 KB |
Output is correct |
51 |
Correct |
40 ms |
6488 KB |
Output is correct |
52 |
Correct |
41 ms |
6488 KB |
Output is correct |
53 |
Correct |
40 ms |
6492 KB |
Output is correct |
54 |
Correct |
40 ms |
6492 KB |
Output is correct |
55 |
Correct |
41 ms |
6492 KB |
Output is correct |
56 |
Correct |
2 ms |
6492 KB |
Output is correct |
57 |
Correct |
28 ms |
6692 KB |
Output is correct |
58 |
Correct |
27 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6624 KB |
Output is correct |
4 |
Correct |
34 ms |
22948 KB |
Output is correct |
5 |
Correct |
33 ms |
19584 KB |
Output is correct |
6 |
Correct |
37 ms |
24072 KB |
Output is correct |
7 |
Correct |
47 ms |
24656 KB |
Output is correct |
8 |
Correct |
48 ms |
24596 KB |
Output is correct |
9 |
Correct |
51 ms |
24588 KB |
Output is correct |
10 |
Correct |
48 ms |
24796 KB |
Output is correct |
11 |
Correct |
47 ms |
24508 KB |
Output is correct |
12 |
Correct |
45 ms |
24608 KB |
Output is correct |
13 |
Correct |
45 ms |
24584 KB |
Output is correct |
14 |
Correct |
45 ms |
24656 KB |
Output is correct |
15 |
Correct |
31 ms |
11860 KB |
Output is correct |
16 |
Correct |
47 ms |
24156 KB |
Output is correct |
17 |
Correct |
33 ms |
21100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Incorrect |
56 ms |
19604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6584 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6492 KB |
Output is correct |
4 |
Incorrect |
26 ms |
8284 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
2 ms |
6492 KB |
Output is correct |
26 |
Correct |
2 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6756 KB |
Output is correct |
30 |
Correct |
34 ms |
6492 KB |
Output is correct |
31 |
Correct |
45 ms |
6492 KB |
Output is correct |
32 |
Correct |
75 ms |
6492 KB |
Output is correct |
33 |
Correct |
74 ms |
6488 KB |
Output is correct |
34 |
Correct |
77 ms |
6492 KB |
Output is correct |
35 |
Correct |
73 ms |
6680 KB |
Output is correct |
36 |
Correct |
77 ms |
6680 KB |
Output is correct |
37 |
Correct |
76 ms |
6668 KB |
Output is correct |
38 |
Correct |
73 ms |
6752 KB |
Output is correct |
39 |
Correct |
75 ms |
6756 KB |
Output is correct |
40 |
Correct |
77 ms |
6744 KB |
Output is correct |
41 |
Correct |
75 ms |
6992 KB |
Output is correct |
42 |
Correct |
75 ms |
6744 KB |
Output is correct |
43 |
Correct |
77 ms |
6744 KB |
Output is correct |
44 |
Correct |
71 ms |
6492 KB |
Output is correct |
45 |
Correct |
76 ms |
6692 KB |
Output is correct |
46 |
Correct |
71 ms |
6492 KB |
Output is correct |
47 |
Correct |
76 ms |
6488 KB |
Output is correct |
48 |
Correct |
75 ms |
6492 KB |
Output is correct |
49 |
Correct |
77 ms |
6744 KB |
Output is correct |
50 |
Correct |
41 ms |
6696 KB |
Output is correct |
51 |
Correct |
40 ms |
6488 KB |
Output is correct |
52 |
Correct |
41 ms |
6488 KB |
Output is correct |
53 |
Correct |
40 ms |
6492 KB |
Output is correct |
54 |
Correct |
40 ms |
6492 KB |
Output is correct |
55 |
Correct |
41 ms |
6492 KB |
Output is correct |
56 |
Correct |
2 ms |
6492 KB |
Output is correct |
57 |
Correct |
28 ms |
6692 KB |
Output is correct |
58 |
Correct |
27 ms |
6492 KB |
Output is correct |
59 |
Correct |
2 ms |
6492 KB |
Output is correct |
60 |
Correct |
1 ms |
6492 KB |
Output is correct |
61 |
Correct |
2 ms |
6624 KB |
Output is correct |
62 |
Correct |
34 ms |
22948 KB |
Output is correct |
63 |
Correct |
33 ms |
19584 KB |
Output is correct |
64 |
Correct |
37 ms |
24072 KB |
Output is correct |
65 |
Correct |
47 ms |
24656 KB |
Output is correct |
66 |
Correct |
48 ms |
24596 KB |
Output is correct |
67 |
Correct |
51 ms |
24588 KB |
Output is correct |
68 |
Correct |
48 ms |
24796 KB |
Output is correct |
69 |
Correct |
47 ms |
24508 KB |
Output is correct |
70 |
Correct |
45 ms |
24608 KB |
Output is correct |
71 |
Correct |
45 ms |
24584 KB |
Output is correct |
72 |
Correct |
45 ms |
24656 KB |
Output is correct |
73 |
Correct |
31 ms |
11860 KB |
Output is correct |
74 |
Correct |
47 ms |
24156 KB |
Output is correct |
75 |
Correct |
33 ms |
21100 KB |
Output is correct |
76 |
Correct |
1 ms |
6488 KB |
Output is correct |
77 |
Incorrect |
56 ms |
19604 KB |
Output isn't correct |
78 |
Halted |
0 ms |
0 KB |
- |