# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
865444 |
2023-10-24T08:29:49 Z |
owoovo |
Tourism (JOI23_tourism) |
C++14 |
|
5000 ms |
21548 KB |
#include<bits/stdc++.h>
#define pii pair<pair<int,int>,int>
#define F first
#define S second
using namespace std;
int n,m,q,bit[100010],v[100010],c[100010],dp[25][100010],depth[100010],u;
vector<int> e[100010];
vector<pii> qu;
bool cmp(pii a, pii b){
return a.S<b.S;
}
void modify(int x,int p){
while(p<=m){
bit[p]+=x;
p+=p&(-p);
}
return ;
}
int que(int p){
int ans=0;
while(p){
ans+=bit[p];
p-=p&(-p);
}
return ans;
}
void dfs(int now,int last){
dp[0][now]=last;
depth[now]=depth[last]+1;
for(auto x:e[now]){
if(x==last)continue;
dfs(x,now);
}
return;
}
int lca(int a,int b){
if(depth[a]>depth[b])swap(a,b);
for(int i=19;i>=0;i--){
if(depth[a]+(1<<i)<=depth[b]){
b=dp[i][b];
}
}
if(a==b)return a;
for(int i=19;i>=0;i--){
if(dp[i][a]!=dp[i][b]){
a=dp[i][a];
b=dp[i][b];
}
}
return dp[0][a];
}
int main(){
u=0;
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;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=m;i++){
cin>>v[i];
}
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;
if(a==m)b=1,u++;
qu.push_back({{a,b},i});
}
dfs(1,1);
for(int i=1;i<=19;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i-1][dp[i-1][j]];
}
}
sort(qu.begin(),qu.end());
int now=q-1-u;
for(int i=m-1;i>0;i--){
int p=lca(v[i],v[i+1]);
int nw=v[i];
while(nw!=p){
if(c[nw]>0)modify(-1,c[nw]);
c[nw]=i;
modify(1,i);
nw=dp[0][nw];
}
nw=v[i+1];
while(nw!=p){
if(c[nw]>0)modify(-1,c[nw]);
c[nw]=i;
modify(1,i);
nw=dp[0][nw];
}
if(c[p]>0)modify(-1,c[p]);
c[p]=i;
modify(1,i);
while(now>=0&&qu[now].F.F==i){
if(qu[now].F.F==qu[now].F.S){
qu[now].F.S=1;
}else{
qu[now].F.S=que(qu[now].F.S-1);
}
now--;
}
}
sort(qu.begin(),qu.end(),cmp);
for(auto x:qu){
cout<<x.F.S<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
10840 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10908 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10856 KB |
Output is correct |
8 |
Correct |
2 ms |
10888 KB |
Output is correct |
9 |
Correct |
2 ms |
10844 KB |
Output is correct |
10 |
Correct |
2 ms |
10844 KB |
Output is correct |
11 |
Correct |
2 ms |
10844 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
2 ms |
10844 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
15 |
Correct |
3 ms |
10844 KB |
Output is correct |
16 |
Correct |
2 ms |
10844 KB |
Output is correct |
17 |
Correct |
2 ms |
10840 KB |
Output is correct |
18 |
Correct |
2 ms |
10844 KB |
Output is correct |
19 |
Correct |
2 ms |
10844 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10844 KB |
Output is correct |
22 |
Correct |
2 ms |
10844 KB |
Output is correct |
23 |
Correct |
2 ms |
10840 KB |
Output is correct |
24 |
Correct |
2 ms |
10844 KB |
Output is correct |
25 |
Correct |
2 ms |
10844 KB |
Output is correct |
26 |
Correct |
2 ms |
10844 KB |
Output is correct |
27 |
Correct |
1 ms |
10844 KB |
Output is correct |
28 |
Correct |
2 ms |
10844 KB |
Output is correct |
29 |
Correct |
2 ms |
10840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
10840 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10908 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10856 KB |
Output is correct |
8 |
Correct |
2 ms |
10888 KB |
Output is correct |
9 |
Correct |
2 ms |
10844 KB |
Output is correct |
10 |
Correct |
2 ms |
10844 KB |
Output is correct |
11 |
Correct |
2 ms |
10844 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
2 ms |
10844 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
15 |
Correct |
3 ms |
10844 KB |
Output is correct |
16 |
Correct |
2 ms |
10844 KB |
Output is correct |
17 |
Correct |
2 ms |
10840 KB |
Output is correct |
18 |
Correct |
2 ms |
10844 KB |
Output is correct |
19 |
Correct |
2 ms |
10844 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10844 KB |
Output is correct |
22 |
Correct |
2 ms |
10844 KB |
Output is correct |
23 |
Correct |
2 ms |
10840 KB |
Output is correct |
24 |
Correct |
2 ms |
10844 KB |
Output is correct |
25 |
Correct |
2 ms |
10844 KB |
Output is correct |
26 |
Correct |
2 ms |
10844 KB |
Output is correct |
27 |
Correct |
1 ms |
10844 KB |
Output is correct |
28 |
Correct |
2 ms |
10844 KB |
Output is correct |
29 |
Correct |
2 ms |
10840 KB |
Output is correct |
30 |
Correct |
3 ms |
10840 KB |
Output is correct |
31 |
Correct |
3 ms |
10840 KB |
Output is correct |
32 |
Correct |
4 ms |
11100 KB |
Output is correct |
33 |
Correct |
5 ms |
11244 KB |
Output is correct |
34 |
Correct |
3 ms |
10844 KB |
Output is correct |
35 |
Correct |
3 ms |
11100 KB |
Output is correct |
36 |
Correct |
3 ms |
11100 KB |
Output is correct |
37 |
Correct |
3 ms |
11100 KB |
Output is correct |
38 |
Correct |
14 ms |
11100 KB |
Output is correct |
39 |
Correct |
15 ms |
11100 KB |
Output is correct |
40 |
Correct |
15 ms |
11148 KB |
Output is correct |
41 |
Correct |
15 ms |
11100 KB |
Output is correct |
42 |
Correct |
15 ms |
11156 KB |
Output is correct |
43 |
Correct |
14 ms |
11096 KB |
Output is correct |
44 |
Correct |
9 ms |
11100 KB |
Output is correct |
45 |
Correct |
7 ms |
10900 KB |
Output is correct |
46 |
Correct |
8 ms |
11100 KB |
Output is correct |
47 |
Correct |
8 ms |
11100 KB |
Output is correct |
48 |
Correct |
7 ms |
11104 KB |
Output is correct |
49 |
Correct |
9 ms |
11096 KB |
Output is correct |
50 |
Correct |
3 ms |
11096 KB |
Output is correct |
51 |
Correct |
3 ms |
10904 KB |
Output is correct |
52 |
Correct |
3 ms |
10900 KB |
Output is correct |
53 |
Correct |
3 ms |
11004 KB |
Output is correct |
54 |
Correct |
3 ms |
11100 KB |
Output is correct |
55 |
Correct |
3 ms |
11100 KB |
Output is correct |
56 |
Correct |
2 ms |
10844 KB |
Output is correct |
57 |
Correct |
2 ms |
11048 KB |
Output is correct |
58 |
Correct |
3 ms |
11096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10840 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Execution timed out |
5053 ms |
17132 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
50 ms |
13148 KB |
Output is correct |
3 |
Correct |
74 ms |
13652 KB |
Output is correct |
4 |
Correct |
63 ms |
15956 KB |
Output is correct |
5 |
Correct |
95 ms |
17232 KB |
Output is correct |
6 |
Correct |
95 ms |
17196 KB |
Output is correct |
7 |
Correct |
94 ms |
17264 KB |
Output is correct |
8 |
Correct |
93 ms |
17236 KB |
Output is correct |
9 |
Correct |
97 ms |
17232 KB |
Output is correct |
10 |
Correct |
106 ms |
17380 KB |
Output is correct |
11 |
Correct |
92 ms |
17272 KB |
Output is correct |
12 |
Correct |
102 ms |
17440 KB |
Output is correct |
13 |
Correct |
97 ms |
17580 KB |
Output is correct |
14 |
Correct |
103 ms |
17744 KB |
Output is correct |
15 |
Correct |
150 ms |
18720 KB |
Output is correct |
16 |
Correct |
98 ms |
19356 KB |
Output is correct |
17 |
Correct |
100 ms |
19248 KB |
Output is correct |
18 |
Correct |
96 ms |
19328 KB |
Output is correct |
19 |
Correct |
1942 ms |
19068 KB |
Output is correct |
20 |
Correct |
2163 ms |
19368 KB |
Output is correct |
21 |
Correct |
1852 ms |
19300 KB |
Output is correct |
22 |
Correct |
1817 ms |
19336 KB |
Output is correct |
23 |
Correct |
2135 ms |
19452 KB |
Output is correct |
24 |
Correct |
2029 ms |
18948 KB |
Output is correct |
25 |
Correct |
2086 ms |
19368 KB |
Output is correct |
26 |
Correct |
1911 ms |
19140 KB |
Output is correct |
27 |
Correct |
2008 ms |
19288 KB |
Output is correct |
28 |
Correct |
1866 ms |
19292 KB |
Output is correct |
29 |
Correct |
2033 ms |
19568 KB |
Output is correct |
30 |
Correct |
1911 ms |
19284 KB |
Output is correct |
31 |
Correct |
1841 ms |
19620 KB |
Output is correct |
32 |
Correct |
1942 ms |
19868 KB |
Output is correct |
33 |
Correct |
1695 ms |
20324 KB |
Output is correct |
34 |
Correct |
2340 ms |
21548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
11092 KB |
Output is correct |
2 |
Correct |
2 ms |
10840 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
111 ms |
15312 KB |
Output is correct |
5 |
Correct |
112 ms |
15308 KB |
Output is correct |
6 |
Correct |
152 ms |
18376 KB |
Output is correct |
7 |
Correct |
135 ms |
19144 KB |
Output is correct |
8 |
Correct |
135 ms |
18896 KB |
Output is correct |
9 |
Correct |
156 ms |
19144 KB |
Output is correct |
10 |
Correct |
134 ms |
19144 KB |
Output is correct |
11 |
Correct |
134 ms |
19140 KB |
Output is correct |
12 |
Correct |
136 ms |
19064 KB |
Output is correct |
13 |
Correct |
134 ms |
19140 KB |
Output is correct |
14 |
Correct |
47 ms |
13112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
10840 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10908 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10856 KB |
Output is correct |
8 |
Correct |
2 ms |
10888 KB |
Output is correct |
9 |
Correct |
2 ms |
10844 KB |
Output is correct |
10 |
Correct |
2 ms |
10844 KB |
Output is correct |
11 |
Correct |
2 ms |
10844 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
2 ms |
10844 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
15 |
Correct |
3 ms |
10844 KB |
Output is correct |
16 |
Correct |
2 ms |
10844 KB |
Output is correct |
17 |
Correct |
2 ms |
10840 KB |
Output is correct |
18 |
Correct |
2 ms |
10844 KB |
Output is correct |
19 |
Correct |
2 ms |
10844 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10844 KB |
Output is correct |
22 |
Correct |
2 ms |
10844 KB |
Output is correct |
23 |
Correct |
2 ms |
10840 KB |
Output is correct |
24 |
Correct |
2 ms |
10844 KB |
Output is correct |
25 |
Correct |
2 ms |
10844 KB |
Output is correct |
26 |
Correct |
2 ms |
10844 KB |
Output is correct |
27 |
Correct |
1 ms |
10844 KB |
Output is correct |
28 |
Correct |
2 ms |
10844 KB |
Output is correct |
29 |
Correct |
2 ms |
10840 KB |
Output is correct |
30 |
Correct |
3 ms |
10840 KB |
Output is correct |
31 |
Correct |
3 ms |
10840 KB |
Output is correct |
32 |
Correct |
4 ms |
11100 KB |
Output is correct |
33 |
Correct |
5 ms |
11244 KB |
Output is correct |
34 |
Correct |
3 ms |
10844 KB |
Output is correct |
35 |
Correct |
3 ms |
11100 KB |
Output is correct |
36 |
Correct |
3 ms |
11100 KB |
Output is correct |
37 |
Correct |
3 ms |
11100 KB |
Output is correct |
38 |
Correct |
14 ms |
11100 KB |
Output is correct |
39 |
Correct |
15 ms |
11100 KB |
Output is correct |
40 |
Correct |
15 ms |
11148 KB |
Output is correct |
41 |
Correct |
15 ms |
11100 KB |
Output is correct |
42 |
Correct |
15 ms |
11156 KB |
Output is correct |
43 |
Correct |
14 ms |
11096 KB |
Output is correct |
44 |
Correct |
9 ms |
11100 KB |
Output is correct |
45 |
Correct |
7 ms |
10900 KB |
Output is correct |
46 |
Correct |
8 ms |
11100 KB |
Output is correct |
47 |
Correct |
8 ms |
11100 KB |
Output is correct |
48 |
Correct |
7 ms |
11104 KB |
Output is correct |
49 |
Correct |
9 ms |
11096 KB |
Output is correct |
50 |
Correct |
3 ms |
11096 KB |
Output is correct |
51 |
Correct |
3 ms |
10904 KB |
Output is correct |
52 |
Correct |
3 ms |
10900 KB |
Output is correct |
53 |
Correct |
3 ms |
11004 KB |
Output is correct |
54 |
Correct |
3 ms |
11100 KB |
Output is correct |
55 |
Correct |
3 ms |
11100 KB |
Output is correct |
56 |
Correct |
2 ms |
10844 KB |
Output is correct |
57 |
Correct |
2 ms |
11048 KB |
Output is correct |
58 |
Correct |
3 ms |
11096 KB |
Output is correct |
59 |
Correct |
2 ms |
10840 KB |
Output is correct |
60 |
Correct |
2 ms |
10844 KB |
Output is correct |
61 |
Correct |
2 ms |
10844 KB |
Output is correct |
62 |
Execution timed out |
5053 ms |
17132 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |