#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;
const int N = 3e5 + 5;
vector <int> v[N];
int ans[N],ord[N],sz[N],heavy[N],head[N],tin[N];
int timer,d[25][N],dep[N],arr[N],n,m;
vector <pii> qr[N];
void dfs(int x,int par){
d[0][x] = par;
dep[x] = dep[par] + 1;
sz[x] = 1;
for (int to: v[x]){
if (to == par) continue;
dfs(to,x);
sz[x] += sz[to];
if (sz[to] > sz[heavy[x]]) heavy[x] = to;
}
}
int lca(int x,int y){
if (dep[x] < dep[y]) swap(x,y);
for (int i = 20; i >= 0; i--)
if (dep[d[i][x]] >= dep[y]) x = d[i][x];
if (x == y) return x;
for (int i = 20; i >= 0; i--)
if (d[i][x] != d[i][y])
x = d[i][x],y = d[i][y];
return d[0][x];
}
void dfs2(int x,int par,int h){
tin[x] = ++timer;
head[x] = h;
if (heavy[x]) dfs2(heavy[x],x,h);
for (int to: v[x]){
if (to == par || to == heavy[x]) continue;
dfs2(to,x,to);
}
}
void addseg(int l,int r,int col){
for (int i = l; i <= r; i++)
arr[i] = col;
}
int get(int x){
int cnt=0;
for (int i = 1; i <= n; i++)
cnt += (arr[i] >= x);
return cnt;
}
void upd(int x,int y,int col){
int c = lca(x,y),cnt=0;
while (head[x] != head[y]){
if (dep[head[x]] < dep[head[y]]) swap(x,y);
addseg(tin[head[x]],tin[x],col);
x = d[0][head[x]];
}
if (dep[x] < dep[y]) swap(x,y);
addseg(tin[y],tin[x],col);
}
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int q;
cin>>n>>m>>q;
for (int i = 1; i < n; i++){
int a,b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
dfs(1,1);
dfs2(1,1,1);
for (int i=1;i<=20;i++)
for (int j=1;j<=n;j++)
d[i][j] = d[i - 1][d[i - 1][j]];
for (int i = 1; i <= m; i++){
cin >> ord[i];
}
for (int i = 1; i <= q; i++){
int l,r;
cin>>l>>r;
qr[r].pb({l,i});
}
for (int i = 1; i <= m; i++){
if (i > 1) upd(ord[i - 1],ord[i],i-1);
upd(ord[i],ord[i],i);
for (auto [x,id]: qr[i]){
ans[id] = get(x);
}
}
for (int i = 1; i <= q; i++)
cout<<ans[i]<<endl;
}
Compilation message
tourism.cpp: In function 'void upd(long long int, long long int, long long int)':
tourism.cpp:68:9: warning: unused variable 'c' [-Wunused-variable]
68 | int c = lca(x,y),cnt=0;
| ^
tourism.cpp:68:22: warning: unused variable 'cnt' [-Wunused-variable]
68 | int c = lca(x,y),cnt=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
67420 KB |
Output is correct |
2 |
Correct |
7 ms |
67384 KB |
Output is correct |
3 |
Correct |
7 ms |
67420 KB |
Output is correct |
4 |
Correct |
8 ms |
67420 KB |
Output is correct |
5 |
Correct |
8 ms |
67376 KB |
Output is correct |
6 |
Correct |
8 ms |
67416 KB |
Output is correct |
7 |
Correct |
8 ms |
67320 KB |
Output is correct |
8 |
Correct |
8 ms |
67420 KB |
Output is correct |
9 |
Correct |
8 ms |
67420 KB |
Output is correct |
10 |
Correct |
8 ms |
67284 KB |
Output is correct |
11 |
Correct |
8 ms |
67416 KB |
Output is correct |
12 |
Correct |
8 ms |
67420 KB |
Output is correct |
13 |
Correct |
8 ms |
67420 KB |
Output is correct |
14 |
Correct |
8 ms |
67248 KB |
Output is correct |
15 |
Correct |
8 ms |
67408 KB |
Output is correct |
16 |
Correct |
9 ms |
67420 KB |
Output is correct |
17 |
Correct |
8 ms |
67420 KB |
Output is correct |
18 |
Correct |
8 ms |
67420 KB |
Output is correct |
19 |
Correct |
8 ms |
67396 KB |
Output is correct |
20 |
Correct |
8 ms |
67448 KB |
Output is correct |
21 |
Correct |
9 ms |
67420 KB |
Output is correct |
22 |
Correct |
8 ms |
67420 KB |
Output is correct |
23 |
Correct |
7 ms |
67420 KB |
Output is correct |
24 |
Correct |
8 ms |
67472 KB |
Output is correct |
25 |
Correct |
8 ms |
67416 KB |
Output is correct |
26 |
Correct |
8 ms |
67252 KB |
Output is correct |
27 |
Correct |
8 ms |
67420 KB |
Output is correct |
28 |
Correct |
8 ms |
67420 KB |
Output is correct |
29 |
Correct |
8 ms |
67420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
67420 KB |
Output is correct |
2 |
Correct |
7 ms |
67384 KB |
Output is correct |
3 |
Correct |
7 ms |
67420 KB |
Output is correct |
4 |
Correct |
8 ms |
67420 KB |
Output is correct |
5 |
Correct |
8 ms |
67376 KB |
Output is correct |
6 |
Correct |
8 ms |
67416 KB |
Output is correct |
7 |
Correct |
8 ms |
67320 KB |
Output is correct |
8 |
Correct |
8 ms |
67420 KB |
Output is correct |
9 |
Correct |
8 ms |
67420 KB |
Output is correct |
10 |
Correct |
8 ms |
67284 KB |
Output is correct |
11 |
Correct |
8 ms |
67416 KB |
Output is correct |
12 |
Correct |
8 ms |
67420 KB |
Output is correct |
13 |
Correct |
8 ms |
67420 KB |
Output is correct |
14 |
Correct |
8 ms |
67248 KB |
Output is correct |
15 |
Correct |
8 ms |
67408 KB |
Output is correct |
16 |
Correct |
9 ms |
67420 KB |
Output is correct |
17 |
Correct |
8 ms |
67420 KB |
Output is correct |
18 |
Correct |
8 ms |
67420 KB |
Output is correct |
19 |
Correct |
8 ms |
67396 KB |
Output is correct |
20 |
Correct |
8 ms |
67448 KB |
Output is correct |
21 |
Correct |
9 ms |
67420 KB |
Output is correct |
22 |
Correct |
8 ms |
67420 KB |
Output is correct |
23 |
Correct |
7 ms |
67420 KB |
Output is correct |
24 |
Correct |
8 ms |
67472 KB |
Output is correct |
25 |
Correct |
8 ms |
67416 KB |
Output is correct |
26 |
Correct |
8 ms |
67252 KB |
Output is correct |
27 |
Correct |
8 ms |
67420 KB |
Output is correct |
28 |
Correct |
8 ms |
67420 KB |
Output is correct |
29 |
Correct |
8 ms |
67420 KB |
Output is correct |
30 |
Correct |
12 ms |
67420 KB |
Output is correct |
31 |
Correct |
12 ms |
67616 KB |
Output is correct |
32 |
Correct |
17 ms |
67420 KB |
Output is correct |
33 |
Correct |
17 ms |
67672 KB |
Output is correct |
34 |
Correct |
14 ms |
67672 KB |
Output is correct |
35 |
Correct |
13 ms |
67676 KB |
Output is correct |
36 |
Correct |
13 ms |
67676 KB |
Output is correct |
37 |
Correct |
15 ms |
67448 KB |
Output is correct |
38 |
Correct |
14 ms |
67672 KB |
Output is correct |
39 |
Correct |
17 ms |
67604 KB |
Output is correct |
40 |
Correct |
14 ms |
67624 KB |
Output is correct |
41 |
Correct |
14 ms |
67760 KB |
Output is correct |
42 |
Correct |
13 ms |
67676 KB |
Output is correct |
43 |
Correct |
13 ms |
67636 KB |
Output is correct |
44 |
Correct |
14 ms |
67676 KB |
Output is correct |
45 |
Correct |
13 ms |
67676 KB |
Output is correct |
46 |
Correct |
13 ms |
67696 KB |
Output is correct |
47 |
Correct |
14 ms |
67672 KB |
Output is correct |
48 |
Correct |
13 ms |
67676 KB |
Output is correct |
49 |
Correct |
15 ms |
67672 KB |
Output is correct |
50 |
Correct |
13 ms |
67420 KB |
Output is correct |
51 |
Correct |
13 ms |
67420 KB |
Output is correct |
52 |
Correct |
13 ms |
67416 KB |
Output is correct |
53 |
Correct |
13 ms |
67588 KB |
Output is correct |
54 |
Correct |
14 ms |
67588 KB |
Output is correct |
55 |
Correct |
14 ms |
67676 KB |
Output is correct |
56 |
Correct |
9 ms |
67420 KB |
Output is correct |
57 |
Correct |
13 ms |
67420 KB |
Output is correct |
58 |
Correct |
13 ms |
67420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
67420 KB |
Output is correct |
2 |
Correct |
8 ms |
67328 KB |
Output is correct |
3 |
Correct |
12 ms |
67336 KB |
Output is correct |
4 |
Correct |
3448 ms |
81488 KB |
Output is correct |
5 |
Correct |
4168 ms |
82468 KB |
Output is correct |
6 |
Correct |
4363 ms |
85420 KB |
Output is correct |
7 |
Execution timed out |
5063 ms |
88552 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
67672 KB |
Output is correct |
2 |
Correct |
106 ms |
74064 KB |
Output is correct |
3 |
Correct |
125 ms |
74844 KB |
Output is correct |
4 |
Correct |
132 ms |
75340 KB |
Output is correct |
5 |
Correct |
62 ms |
77036 KB |
Output is correct |
6 |
Correct |
62 ms |
78424 KB |
Output is correct |
7 |
Correct |
72 ms |
77140 KB |
Output is correct |
8 |
Correct |
69 ms |
77140 KB |
Output is correct |
9 |
Correct |
70 ms |
77052 KB |
Output is correct |
10 |
Correct |
89 ms |
78420 KB |
Output is correct |
11 |
Correct |
130 ms |
77136 KB |
Output is correct |
12 |
Correct |
275 ms |
77292 KB |
Output is correct |
13 |
Correct |
758 ms |
77692 KB |
Output is correct |
14 |
Correct |
2076 ms |
79952 KB |
Output is correct |
15 |
Execution timed out |
5048 ms |
83304 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
67420 KB |
Output is correct |
2 |
Correct |
8 ms |
67280 KB |
Output is correct |
3 |
Correct |
10 ms |
67420 KB |
Output is correct |
4 |
Correct |
3664 ms |
79468 KB |
Output is correct |
5 |
Correct |
3411 ms |
77648 KB |
Output is correct |
6 |
Execution timed out |
5059 ms |
81236 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
67420 KB |
Output is correct |
2 |
Correct |
7 ms |
67384 KB |
Output is correct |
3 |
Correct |
7 ms |
67420 KB |
Output is correct |
4 |
Correct |
8 ms |
67420 KB |
Output is correct |
5 |
Correct |
8 ms |
67376 KB |
Output is correct |
6 |
Correct |
8 ms |
67416 KB |
Output is correct |
7 |
Correct |
8 ms |
67320 KB |
Output is correct |
8 |
Correct |
8 ms |
67420 KB |
Output is correct |
9 |
Correct |
8 ms |
67420 KB |
Output is correct |
10 |
Correct |
8 ms |
67284 KB |
Output is correct |
11 |
Correct |
8 ms |
67416 KB |
Output is correct |
12 |
Correct |
8 ms |
67420 KB |
Output is correct |
13 |
Correct |
8 ms |
67420 KB |
Output is correct |
14 |
Correct |
8 ms |
67248 KB |
Output is correct |
15 |
Correct |
8 ms |
67408 KB |
Output is correct |
16 |
Correct |
9 ms |
67420 KB |
Output is correct |
17 |
Correct |
8 ms |
67420 KB |
Output is correct |
18 |
Correct |
8 ms |
67420 KB |
Output is correct |
19 |
Correct |
8 ms |
67396 KB |
Output is correct |
20 |
Correct |
8 ms |
67448 KB |
Output is correct |
21 |
Correct |
9 ms |
67420 KB |
Output is correct |
22 |
Correct |
8 ms |
67420 KB |
Output is correct |
23 |
Correct |
7 ms |
67420 KB |
Output is correct |
24 |
Correct |
8 ms |
67472 KB |
Output is correct |
25 |
Correct |
8 ms |
67416 KB |
Output is correct |
26 |
Correct |
8 ms |
67252 KB |
Output is correct |
27 |
Correct |
8 ms |
67420 KB |
Output is correct |
28 |
Correct |
8 ms |
67420 KB |
Output is correct |
29 |
Correct |
8 ms |
67420 KB |
Output is correct |
30 |
Correct |
12 ms |
67420 KB |
Output is correct |
31 |
Correct |
12 ms |
67616 KB |
Output is correct |
32 |
Correct |
17 ms |
67420 KB |
Output is correct |
33 |
Correct |
17 ms |
67672 KB |
Output is correct |
34 |
Correct |
14 ms |
67672 KB |
Output is correct |
35 |
Correct |
13 ms |
67676 KB |
Output is correct |
36 |
Correct |
13 ms |
67676 KB |
Output is correct |
37 |
Correct |
15 ms |
67448 KB |
Output is correct |
38 |
Correct |
14 ms |
67672 KB |
Output is correct |
39 |
Correct |
17 ms |
67604 KB |
Output is correct |
40 |
Correct |
14 ms |
67624 KB |
Output is correct |
41 |
Correct |
14 ms |
67760 KB |
Output is correct |
42 |
Correct |
13 ms |
67676 KB |
Output is correct |
43 |
Correct |
13 ms |
67636 KB |
Output is correct |
44 |
Correct |
14 ms |
67676 KB |
Output is correct |
45 |
Correct |
13 ms |
67676 KB |
Output is correct |
46 |
Correct |
13 ms |
67696 KB |
Output is correct |
47 |
Correct |
14 ms |
67672 KB |
Output is correct |
48 |
Correct |
13 ms |
67676 KB |
Output is correct |
49 |
Correct |
15 ms |
67672 KB |
Output is correct |
50 |
Correct |
13 ms |
67420 KB |
Output is correct |
51 |
Correct |
13 ms |
67420 KB |
Output is correct |
52 |
Correct |
13 ms |
67416 KB |
Output is correct |
53 |
Correct |
13 ms |
67588 KB |
Output is correct |
54 |
Correct |
14 ms |
67588 KB |
Output is correct |
55 |
Correct |
14 ms |
67676 KB |
Output is correct |
56 |
Correct |
9 ms |
67420 KB |
Output is correct |
57 |
Correct |
13 ms |
67420 KB |
Output is correct |
58 |
Correct |
13 ms |
67420 KB |
Output is correct |
59 |
Correct |
8 ms |
67420 KB |
Output is correct |
60 |
Correct |
8 ms |
67328 KB |
Output is correct |
61 |
Correct |
12 ms |
67336 KB |
Output is correct |
62 |
Correct |
3448 ms |
81488 KB |
Output is correct |
63 |
Correct |
4168 ms |
82468 KB |
Output is correct |
64 |
Correct |
4363 ms |
85420 KB |
Output is correct |
65 |
Execution timed out |
5063 ms |
88552 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |