# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
789298 |
2023-07-21T09:02:16 Z |
박상훈(#10042) |
Tourism (JOI23_tourism) |
C++17 |
|
5000 ms |
16332 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int B = 400, INF = 1e9 + 100;
vector<int> adj[100100];
int a[100100], ans[100100], cnt[100100], val;
multiset<pair<int, int>> st;
int in[100100], out[100100], dep[100100], cnti;
int on[100100], C[100100], par[100100], chk[100100];
struct Query{
int s, e, i;
Query(){}
Query(int _s, int _e, int _i): s(_s), e(_e), i(_i) {}
bool operator < (const Query &Q) const{
if (s / B == Q.s / B){
if ((s / B) % 2 == 0) return e < Q.e;
return e > Q.e;
}
return s / B < Q.s / B;
}
}Q[100100];
struct Seg{
pair<int, int> tree[400400];
int sz;
void init(int n){
sz = n;
// for (int i=sz;i<sz*2;i++) printf("(%d, %d) ", tree[i].first, tree[i].second);
// printf("\n");
for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
int query(int l, int r){
// printf(" query %d to %d\n", l, r);
++r;
pair<int, int> ret = {INF, 0};
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret.second;
}
}rmq;
void dfs(int s, int pa = 0){
in[s] = ++cnti;
dep[s] = dep[pa] + 1;
rmq.tree[cnti + rmq.sz] = {dep[s], s};
par[s] = pa;
for (auto &v:adj[s]) if (v!=pa){
dfs(v, s);
++cnti;
rmq.tree[cnti + rmq.sz] = {dep[s], s};
}
// out[s] = ++cnti;
// rmq.tree[cnti + rmq.sz] = {dep[s], s};
}
int dist(int x, int y){
int lca = rmq.query(min(in[x], in[y]), max(in[x], in[y]));
// printf(" calc %d %d -> %d (lca = %d)\n", x, y, dep[x] + dep[y] - dep[lca] * 2, lca);
return dep[x] + dep[y] - dep[lca] * 2;
}
void push(int x){
x = a[x];
// printf("push %d\n", x);
cnt[x]++;
if (cnt[x]==1){
chk[dep[x]]++;
for (int s=x;s;s=par[s]){
on[s]++;
if (on[s]==1){
C[dep[s]]++;
val++;
}
}
// auto iter = st.emplace(in[x], x);
// auto prv = (iter==st.begin())?(prev(st.end())):(prev(iter));
// auto nxt = (next(iter)==st.end())?(st.begin()):(next(iter));
// val -= dist(prv->second, nxt->second);
// val += dist(prv->second, iter->second);
// val += dist(iter->second, nxt->second);
}
// printf(" ok val = %d\n", val);
}
void pop(int x){
x = a[x];
// printf("pop %d\n", x);
cnt[x]--;
if (cnt[x]==0){
chk[dep[x]]--;
for (int s=x;s;s=par[s]){
on[s]--;
if (on[s]==0){
C[dep[s]]--;
val--;
}
}
// auto iter = st.find(pair<int, int>(in[x], x));
// assert(iter!=st.end());
// auto prv = (iter==st.begin())?(prev(st.end())):(prev(iter));
// auto nxt = (next(iter)==st.end())?(st.begin()):(next(iter));
// val += dist(prv->second, nxt->second);
// val -= dist(prv->second, iter->second);
// val -= dist(iter->second, nxt->second);
// st.erase(iter);
}
// printf(" ok val = %d\n", val);
}
int ofs(){
int ret = 0;
for (int i=1;;i++){
if (C[i]==1 && chk[i]==0) ret = i-1;
else if (C[i]==1){
ret = i-1;
break;
}
else break;
}
return ret;
}
int main(){
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i=1;i<=n-1;i++){
int x, y;
scanf("%d %d", &x, &y);
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i=1;i<=m;i++) scanf("%d", a+i);
for (int i=1;i<=q;i++){
scanf("%d %d", &Q[i].s, &Q[i].e);
Q[i].i = i;
}
rmq.sz = n*2+10;
dfs(1);
rmq.init(n*2+10);
sort(Q+1, Q+q+1);
int l = 1, r = 0;
for (int i=1;i<=q;i++){
while(r<Q[i].e){
++r;
push(r);
}
while(l>Q[i].s){
--l;
push(l);
}
while(r>Q[i].e){
pop(r);
r--;
}
while(l<Q[i].s){
pop(l);
l++;
}
ans[Q[i].i] = val - ofs();
// printf("ok %d to %d -> %d - %d\n", Q[i].s, Q[i].e, val, ofs());
}
for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:158:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | for (int i=1;i<=m;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
tourism.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d %d", &Q[i].s, &Q[i].e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5716 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
3 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
3 ms |
5844 KB |
Output is correct |
8 |
Correct |
3 ms |
5800 KB |
Output is correct |
9 |
Correct |
4 ms |
5804 KB |
Output is correct |
10 |
Correct |
3 ms |
5844 KB |
Output is correct |
11 |
Correct |
3 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
3 ms |
5844 KB |
Output is correct |
14 |
Correct |
3 ms |
5844 KB |
Output is correct |
15 |
Correct |
6 ms |
5844 KB |
Output is correct |
16 |
Correct |
6 ms |
5844 KB |
Output is correct |
17 |
Correct |
6 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
7 ms |
5880 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
6 ms |
5844 KB |
Output is correct |
22 |
Correct |
3 ms |
5808 KB |
Output is correct |
23 |
Correct |
3 ms |
5800 KB |
Output is correct |
24 |
Correct |
3 ms |
5844 KB |
Output is correct |
25 |
Correct |
3 ms |
5872 KB |
Output is correct |
26 |
Correct |
3 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
4 ms |
5892 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5716 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
3 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
3 ms |
5844 KB |
Output is correct |
8 |
Correct |
3 ms |
5800 KB |
Output is correct |
9 |
Correct |
4 ms |
5804 KB |
Output is correct |
10 |
Correct |
3 ms |
5844 KB |
Output is correct |
11 |
Correct |
3 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
3 ms |
5844 KB |
Output is correct |
14 |
Correct |
3 ms |
5844 KB |
Output is correct |
15 |
Correct |
6 ms |
5844 KB |
Output is correct |
16 |
Correct |
6 ms |
5844 KB |
Output is correct |
17 |
Correct |
6 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
7 ms |
5880 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
6 ms |
5844 KB |
Output is correct |
22 |
Correct |
3 ms |
5808 KB |
Output is correct |
23 |
Correct |
3 ms |
5800 KB |
Output is correct |
24 |
Correct |
3 ms |
5844 KB |
Output is correct |
25 |
Correct |
3 ms |
5872 KB |
Output is correct |
26 |
Correct |
3 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
4 ms |
5892 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
30 |
Correct |
7 ms |
5972 KB |
Output is correct |
31 |
Correct |
8 ms |
5972 KB |
Output is correct |
32 |
Correct |
14 ms |
6032 KB |
Output is correct |
33 |
Correct |
13 ms |
5972 KB |
Output is correct |
34 |
Correct |
11 ms |
6016 KB |
Output is correct |
35 |
Correct |
4 ms |
6012 KB |
Output is correct |
36 |
Correct |
4 ms |
6016 KB |
Output is correct |
37 |
Correct |
4 ms |
5972 KB |
Output is correct |
38 |
Correct |
236 ms |
6112 KB |
Output is correct |
39 |
Correct |
243 ms |
6120 KB |
Output is correct |
40 |
Correct |
276 ms |
6132 KB |
Output is correct |
41 |
Correct |
26 ms |
6100 KB |
Output is correct |
42 |
Correct |
24 ms |
6172 KB |
Output is correct |
43 |
Correct |
21 ms |
6068 KB |
Output is correct |
44 |
Correct |
139 ms |
6064 KB |
Output is correct |
45 |
Correct |
80 ms |
6036 KB |
Output is correct |
46 |
Correct |
180 ms |
6060 KB |
Output is correct |
47 |
Correct |
10 ms |
6068 KB |
Output is correct |
48 |
Correct |
9 ms |
5972 KB |
Output is correct |
49 |
Correct |
12 ms |
5972 KB |
Output is correct |
50 |
Correct |
5 ms |
5972 KB |
Output is correct |
51 |
Correct |
7 ms |
5972 KB |
Output is correct |
52 |
Correct |
5 ms |
5972 KB |
Output is correct |
53 |
Correct |
5 ms |
5972 KB |
Output is correct |
54 |
Correct |
5 ms |
5972 KB |
Output is correct |
55 |
Correct |
6 ms |
5944 KB |
Output is correct |
56 |
Correct |
4 ms |
5876 KB |
Output is correct |
57 |
Correct |
3 ms |
5940 KB |
Output is correct |
58 |
Correct |
4 ms |
5972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5844 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
4 ms |
5844 KB |
Output is correct |
4 |
Execution timed out |
5062 ms |
14920 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
44 ms |
8916 KB |
Output is correct |
3 |
Correct |
58 ms |
10400 KB |
Output is correct |
4 |
Correct |
57 ms |
10800 KB |
Output is correct |
5 |
Correct |
51 ms |
13056 KB |
Output is correct |
6 |
Correct |
58 ms |
13112 KB |
Output is correct |
7 |
Correct |
60 ms |
13092 KB |
Output is correct |
8 |
Correct |
60 ms |
13116 KB |
Output is correct |
9 |
Correct |
61 ms |
13040 KB |
Output is correct |
10 |
Correct |
70 ms |
13048 KB |
Output is correct |
11 |
Correct |
90 ms |
13072 KB |
Output is correct |
12 |
Correct |
91 ms |
13208 KB |
Output is correct |
13 |
Correct |
90 ms |
13324 KB |
Output is correct |
14 |
Correct |
86 ms |
13916 KB |
Output is correct |
15 |
Correct |
118 ms |
16184 KB |
Output is correct |
16 |
Correct |
82 ms |
13376 KB |
Output is correct |
17 |
Correct |
77 ms |
13348 KB |
Output is correct |
18 |
Correct |
77 ms |
13416 KB |
Output is correct |
19 |
Correct |
581 ms |
13252 KB |
Output is correct |
20 |
Correct |
719 ms |
13100 KB |
Output is correct |
21 |
Correct |
769 ms |
13144 KB |
Output is correct |
22 |
Correct |
1091 ms |
13168 KB |
Output is correct |
23 |
Correct |
1240 ms |
13260 KB |
Output is correct |
24 |
Correct |
1141 ms |
13144 KB |
Output is correct |
25 |
Correct |
1184 ms |
13136 KB |
Output is correct |
26 |
Correct |
1965 ms |
13200 KB |
Output is correct |
27 |
Correct |
1970 ms |
13192 KB |
Output is correct |
28 |
Correct |
1787 ms |
13152 KB |
Output is correct |
29 |
Correct |
2935 ms |
13336 KB |
Output is correct |
30 |
Correct |
4151 ms |
13328 KB |
Output is correct |
31 |
Correct |
2514 ms |
13412 KB |
Output is correct |
32 |
Correct |
2858 ms |
13752 KB |
Output is correct |
33 |
Correct |
2430 ms |
14624 KB |
Output is correct |
34 |
Execution timed out |
5074 ms |
15896 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
4 ms |
5844 KB |
Output is correct |
4 |
Correct |
845 ms |
11960 KB |
Output is correct |
5 |
Correct |
843 ms |
13248 KB |
Output is correct |
6 |
Correct |
1188 ms |
15168 KB |
Output is correct |
7 |
Correct |
1329 ms |
16332 KB |
Output is correct |
8 |
Correct |
1261 ms |
16228 KB |
Output is correct |
9 |
Correct |
1351 ms |
16208 KB |
Output is correct |
10 |
Correct |
1289 ms |
16224 KB |
Output is correct |
11 |
Correct |
1297 ms |
16212 KB |
Output is correct |
12 |
Correct |
1296 ms |
16204 KB |
Output is correct |
13 |
Correct |
1300 ms |
16208 KB |
Output is correct |
14 |
Correct |
109 ms |
9256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5716 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
3 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
3 ms |
5844 KB |
Output is correct |
8 |
Correct |
3 ms |
5800 KB |
Output is correct |
9 |
Correct |
4 ms |
5804 KB |
Output is correct |
10 |
Correct |
3 ms |
5844 KB |
Output is correct |
11 |
Correct |
3 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
3 ms |
5844 KB |
Output is correct |
14 |
Correct |
3 ms |
5844 KB |
Output is correct |
15 |
Correct |
6 ms |
5844 KB |
Output is correct |
16 |
Correct |
6 ms |
5844 KB |
Output is correct |
17 |
Correct |
6 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
7 ms |
5880 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
6 ms |
5844 KB |
Output is correct |
22 |
Correct |
3 ms |
5808 KB |
Output is correct |
23 |
Correct |
3 ms |
5800 KB |
Output is correct |
24 |
Correct |
3 ms |
5844 KB |
Output is correct |
25 |
Correct |
3 ms |
5872 KB |
Output is correct |
26 |
Correct |
3 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
4 ms |
5892 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
30 |
Correct |
7 ms |
5972 KB |
Output is correct |
31 |
Correct |
8 ms |
5972 KB |
Output is correct |
32 |
Correct |
14 ms |
6032 KB |
Output is correct |
33 |
Correct |
13 ms |
5972 KB |
Output is correct |
34 |
Correct |
11 ms |
6016 KB |
Output is correct |
35 |
Correct |
4 ms |
6012 KB |
Output is correct |
36 |
Correct |
4 ms |
6016 KB |
Output is correct |
37 |
Correct |
4 ms |
5972 KB |
Output is correct |
38 |
Correct |
236 ms |
6112 KB |
Output is correct |
39 |
Correct |
243 ms |
6120 KB |
Output is correct |
40 |
Correct |
276 ms |
6132 KB |
Output is correct |
41 |
Correct |
26 ms |
6100 KB |
Output is correct |
42 |
Correct |
24 ms |
6172 KB |
Output is correct |
43 |
Correct |
21 ms |
6068 KB |
Output is correct |
44 |
Correct |
139 ms |
6064 KB |
Output is correct |
45 |
Correct |
80 ms |
6036 KB |
Output is correct |
46 |
Correct |
180 ms |
6060 KB |
Output is correct |
47 |
Correct |
10 ms |
6068 KB |
Output is correct |
48 |
Correct |
9 ms |
5972 KB |
Output is correct |
49 |
Correct |
12 ms |
5972 KB |
Output is correct |
50 |
Correct |
5 ms |
5972 KB |
Output is correct |
51 |
Correct |
7 ms |
5972 KB |
Output is correct |
52 |
Correct |
5 ms |
5972 KB |
Output is correct |
53 |
Correct |
5 ms |
5972 KB |
Output is correct |
54 |
Correct |
5 ms |
5972 KB |
Output is correct |
55 |
Correct |
6 ms |
5944 KB |
Output is correct |
56 |
Correct |
4 ms |
5876 KB |
Output is correct |
57 |
Correct |
3 ms |
5940 KB |
Output is correct |
58 |
Correct |
4 ms |
5972 KB |
Output is correct |
59 |
Correct |
2 ms |
5844 KB |
Output is correct |
60 |
Correct |
3 ms |
5844 KB |
Output is correct |
61 |
Correct |
4 ms |
5844 KB |
Output is correct |
62 |
Execution timed out |
5062 ms |
14920 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |