#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
const int MAXN=1e5+10;
const int BUCK=450;
struct Query {
int l, r;
int ind;
bool friend operator < (Query a, Query b) {
return a.r>b.r;
}
};
Query que[MAXN];
vector <int> v[MAXN];
vector <int> arr, isl;
int c[MAXN];
int fe[MAXN], le[MAXN], in[MAXN], dep[MAXN];
int sp[2*MAXN][20], stepen[2*MAXN];
int n, m, q, cnt;
bool cmpi(int a, int b) {
return in[a]<in[b];
}
void dfs(int x, int p) {
in[x]=cnt;
cnt++;
fe[x]=arr.size();
for (auto i:v[x]) {
if (i==p) continue;
arr.push_back(x);
dep[i]=dep[x]+1;
dfs(i,x);
}
le[x]=arr.size();
arr.push_back(x);
}
void sparce_table() {
int kn=arr.size();
for (int i=0;i<kn;i++) sp[i][0]=arr[i];
for (int i=1;(1<<i)<=kn;i++) {
for (int j=0;j+(1<<i)-1<kn;j++) {
int i1, i2;
i1=sp[j][i-1];
i2=sp[j + (1 << (i-1))][i-1];
if (dep[i1]<dep[i2]) sp[j][i]=i1;
else sp[j][i]=i2;
}
}
int st=0;
for (int i=1;i<=kn;i++) {
if ((1 << (st+1))<i) st++;
stepen[i]=st;
}
}
int lca(int l, int r) {
int st=stepen[r-l+1];
int i1, i2;
i1=sp[l][st];
i2=sp[r - (1<<st)+1][st];
if (dep[i1]<dep[i2]) return i1;
return i2;
}
int getdist(int a, int b) {
if (in[a]>in[b]) swap(a,b);
return dep[a]+dep[b]-2*dep[lca(fe[a],fe[b])];
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> n >> m >> q;
for (int i=0;i<n-1;i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
cnt=1;
dfs(1,-1);
sparce_table();
for (int i=1;i<=m;i++) cin >> c[i];
int ans;
for (int i=0;i<q;i++) {
cin >> que[i].l >> que[i].r;
if (!isl.empty()) isl.clear();
for (int j=que[i].l;j<=que[i].r;j++) isl.push_back(c[j]);
sort(isl.begin(),isl.end(),cmpi);
ans=0;
for (int j=1;j<isl.size();j++) ans+=getdist(isl[j-1],isl[j]);
if (isl.size()>1) ans+=getdist(isl[0],isl.back());
cout << ans/2+1 << endl;
que[i].ind=i;
}
return 0;
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j=1;j<isl.size();j++) ans+=getdist(isl[j-1],isl[j]);
| ~^~~~~~~~~~~
# |
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 |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 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 |
3 ms |
6492 KB |
Output is correct |
10 |
Correct |
3 ms |
6492 KB |
Output is correct |
11 |
Correct |
3 ms |
6492 KB |
Output is correct |
12 |
Correct |
6 ms |
6492 KB |
Output is correct |
13 |
Correct |
6 ms |
6488 KB |
Output is correct |
14 |
Correct |
6 ms |
6492 KB |
Output is correct |
15 |
Correct |
4 ms |
6712 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
3 ms |
6492 KB |
Output is correct |
18 |
Correct |
3 ms |
6704 KB |
Output is correct |
19 |
Correct |
4 ms |
6504 KB |
Output is correct |
20 |
Correct |
3 ms |
6492 KB |
Output is correct |
21 |
Correct |
3 ms |
6492 KB |
Output is correct |
22 |
Correct |
3 ms |
6492 KB |
Output is correct |
23 |
Correct |
3 ms |
6492 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6492 KB |
Output is correct |
26 |
Correct |
3 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 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 |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 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 |
3 ms |
6492 KB |
Output is correct |
10 |
Correct |
3 ms |
6492 KB |
Output is correct |
11 |
Correct |
3 ms |
6492 KB |
Output is correct |
12 |
Correct |
6 ms |
6492 KB |
Output is correct |
13 |
Correct |
6 ms |
6488 KB |
Output is correct |
14 |
Correct |
6 ms |
6492 KB |
Output is correct |
15 |
Correct |
4 ms |
6712 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
3 ms |
6492 KB |
Output is correct |
18 |
Correct |
3 ms |
6704 KB |
Output is correct |
19 |
Correct |
4 ms |
6504 KB |
Output is correct |
20 |
Correct |
3 ms |
6492 KB |
Output is correct |
21 |
Correct |
3 ms |
6492 KB |
Output is correct |
22 |
Correct |
3 ms |
6492 KB |
Output is correct |
23 |
Correct |
3 ms |
6492 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6492 KB |
Output is correct |
26 |
Correct |
3 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
46 ms |
6744 KB |
Output is correct |
31 |
Correct |
62 ms |
6804 KB |
Output is correct |
32 |
Correct |
89 ms |
6748 KB |
Output is correct |
33 |
Correct |
91 ms |
6748 KB |
Output is correct |
34 |
Correct |
90 ms |
6748 KB |
Output is correct |
35 |
Correct |
286 ms |
6996 KB |
Output is correct |
36 |
Correct |
283 ms |
6840 KB |
Output is correct |
37 |
Correct |
287 ms |
7084 KB |
Output is correct |
38 |
Correct |
102 ms |
6748 KB |
Output is correct |
39 |
Correct |
89 ms |
6744 KB |
Output is correct |
40 |
Correct |
87 ms |
6928 KB |
Output is correct |
41 |
Correct |
284 ms |
6996 KB |
Output is correct |
42 |
Correct |
282 ms |
6972 KB |
Output is correct |
43 |
Correct |
300 ms |
6748 KB |
Output is correct |
44 |
Correct |
86 ms |
7136 KB |
Output is correct |
45 |
Correct |
90 ms |
6872 KB |
Output is correct |
46 |
Correct |
91 ms |
6892 KB |
Output is correct |
47 |
Correct |
284 ms |
6744 KB |
Output is correct |
48 |
Correct |
284 ms |
6748 KB |
Output is correct |
49 |
Correct |
282 ms |
6892 KB |
Output is correct |
50 |
Correct |
94 ms |
6992 KB |
Output is correct |
51 |
Correct |
93 ms |
7092 KB |
Output is correct |
52 |
Correct |
92 ms |
6744 KB |
Output is correct |
53 |
Correct |
88 ms |
6748 KB |
Output is correct |
54 |
Correct |
89 ms |
6744 KB |
Output is correct |
55 |
Correct |
92 ms |
6848 KB |
Output is correct |
56 |
Correct |
28 ms |
6492 KB |
Output is correct |
57 |
Correct |
2 ms |
6748 KB |
Output is correct |
58 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6576 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
28 ms |
6724 KB |
Output is correct |
4 |
Execution timed out |
5039 ms |
22328 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
27 ms |
18344 KB |
Output is correct |
3 |
Correct |
38 ms |
18696 KB |
Output is correct |
4 |
Correct |
33 ms |
21192 KB |
Output is correct |
5 |
Correct |
62 ms |
27848 KB |
Output is correct |
6 |
Correct |
64 ms |
27340 KB |
Output is correct |
7 |
Correct |
62 ms |
27000 KB |
Output is correct |
8 |
Correct |
61 ms |
26896 KB |
Output is correct |
9 |
Correct |
58 ms |
27080 KB |
Output is correct |
10 |
Correct |
60 ms |
27084 KB |
Output is correct |
11 |
Correct |
58 ms |
27092 KB |
Output is correct |
12 |
Correct |
58 ms |
27080 KB |
Output is correct |
13 |
Correct |
68 ms |
27336 KB |
Output is correct |
14 |
Correct |
69 ms |
28032 KB |
Output is correct |
15 |
Correct |
72 ms |
29460 KB |
Output is correct |
16 |
Correct |
63 ms |
27588 KB |
Output is correct |
17 |
Correct |
72 ms |
27568 KB |
Output is correct |
18 |
Correct |
66 ms |
27592 KB |
Output is correct |
19 |
Correct |
58 ms |
27844 KB |
Output is correct |
20 |
Correct |
59 ms |
27236 KB |
Output is correct |
21 |
Correct |
70 ms |
27080 KB |
Output is correct |
22 |
Correct |
74 ms |
27080 KB |
Output is correct |
23 |
Correct |
77 ms |
26928 KB |
Output is correct |
24 |
Correct |
59 ms |
27076 KB |
Output is correct |
25 |
Correct |
56 ms |
27068 KB |
Output is correct |
26 |
Correct |
58 ms |
27120 KB |
Output is correct |
27 |
Correct |
53 ms |
27076 KB |
Output is correct |
28 |
Correct |
60 ms |
27076 KB |
Output is correct |
29 |
Correct |
55 ms |
27100 KB |
Output is correct |
30 |
Correct |
56 ms |
27076 KB |
Output is correct |
31 |
Correct |
54 ms |
27328 KB |
Output is correct |
32 |
Correct |
54 ms |
27424 KB |
Output is correct |
33 |
Correct |
61 ms |
28352 KB |
Output is correct |
34 |
Correct |
84 ms |
29636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
29 ms |
6704 KB |
Output is correct |
4 |
Execution timed out |
5027 ms |
19144 KB |
Time limit exceeded |
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 |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 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 |
3 ms |
6492 KB |
Output is correct |
10 |
Correct |
3 ms |
6492 KB |
Output is correct |
11 |
Correct |
3 ms |
6492 KB |
Output is correct |
12 |
Correct |
6 ms |
6492 KB |
Output is correct |
13 |
Correct |
6 ms |
6488 KB |
Output is correct |
14 |
Correct |
6 ms |
6492 KB |
Output is correct |
15 |
Correct |
4 ms |
6712 KB |
Output is correct |
16 |
Correct |
3 ms |
6492 KB |
Output is correct |
17 |
Correct |
3 ms |
6492 KB |
Output is correct |
18 |
Correct |
3 ms |
6704 KB |
Output is correct |
19 |
Correct |
4 ms |
6504 KB |
Output is correct |
20 |
Correct |
3 ms |
6492 KB |
Output is correct |
21 |
Correct |
3 ms |
6492 KB |
Output is correct |
22 |
Correct |
3 ms |
6492 KB |
Output is correct |
23 |
Correct |
3 ms |
6492 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6492 KB |
Output is correct |
26 |
Correct |
3 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
46 ms |
6744 KB |
Output is correct |
31 |
Correct |
62 ms |
6804 KB |
Output is correct |
32 |
Correct |
89 ms |
6748 KB |
Output is correct |
33 |
Correct |
91 ms |
6748 KB |
Output is correct |
34 |
Correct |
90 ms |
6748 KB |
Output is correct |
35 |
Correct |
286 ms |
6996 KB |
Output is correct |
36 |
Correct |
283 ms |
6840 KB |
Output is correct |
37 |
Correct |
287 ms |
7084 KB |
Output is correct |
38 |
Correct |
102 ms |
6748 KB |
Output is correct |
39 |
Correct |
89 ms |
6744 KB |
Output is correct |
40 |
Correct |
87 ms |
6928 KB |
Output is correct |
41 |
Correct |
284 ms |
6996 KB |
Output is correct |
42 |
Correct |
282 ms |
6972 KB |
Output is correct |
43 |
Correct |
300 ms |
6748 KB |
Output is correct |
44 |
Correct |
86 ms |
7136 KB |
Output is correct |
45 |
Correct |
90 ms |
6872 KB |
Output is correct |
46 |
Correct |
91 ms |
6892 KB |
Output is correct |
47 |
Correct |
284 ms |
6744 KB |
Output is correct |
48 |
Correct |
284 ms |
6748 KB |
Output is correct |
49 |
Correct |
282 ms |
6892 KB |
Output is correct |
50 |
Correct |
94 ms |
6992 KB |
Output is correct |
51 |
Correct |
93 ms |
7092 KB |
Output is correct |
52 |
Correct |
92 ms |
6744 KB |
Output is correct |
53 |
Correct |
88 ms |
6748 KB |
Output is correct |
54 |
Correct |
89 ms |
6744 KB |
Output is correct |
55 |
Correct |
92 ms |
6848 KB |
Output is correct |
56 |
Correct |
28 ms |
6492 KB |
Output is correct |
57 |
Correct |
2 ms |
6748 KB |
Output is correct |
58 |
Correct |
2 ms |
6748 KB |
Output is correct |
59 |
Correct |
2 ms |
6576 KB |
Output is correct |
60 |
Correct |
2 ms |
6492 KB |
Output is correct |
61 |
Correct |
28 ms |
6724 KB |
Output is correct |
62 |
Execution timed out |
5039 ms |
22328 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |