# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
789123 |
2023-07-21T05:34:44 Z |
박상훈(#10042) |
Tourism (JOI23_tourism) |
C++17 |
|
5000 ms |
22112 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int B = 400, INF = 1e9 + 100;
int n;
vector<int> adj[100100];
int a[100100], ans[100100], cnt[100100], val;
multiset<pair<int, int>> st;
int in[100100], out[100100], dep[100100], INV[100100], cnti;
int dfn[100100], cntd;
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;
struct Seg2{
int tree[400400];
int sz;
void init(int n){
sz = n;
fill(tree, tree+sz*2, -INF);
}
void update(int p, int x){
p += sz;
tree[p] = x;
for(p>>=1;p;p>>=1) tree[p] = max(tree[p<<1], tree[p<<1|1]);
}
int query(int l, int r){
// printf(" query %d to %d\n", l, r);
++r;
int ret = -INF;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = max(ret, tree[l++]);
if (r&1) ret = max(ret, tree[--r]);
}
return ret;
}
}prf;
struct Seg3{
int tree[400400];
int sz;
void init(int n){
sz = n;
fill(tree, tree+sz*2, INF);
}
void update(int p, int x){
p += sz;
tree[p] = x;
for(p>>=1;p;p>>=1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
}
int query(int l, int r){
// printf(" query %d to %d\n", l, r);
++r;
int ret = INF;
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;
}
}suf;
void dfs(int s, int pa = 0){
in[s] = ++cnti;
dep[s] = dep[pa] + 1;
rmq.tree[cnti + rmq.sz] = {dep[s], s};
dfn[s] = ++cntd;
INV[cntd] = s;
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;
}
int s0, e0;
void push(int x){
x = a[x];
// printf("push %d\n", x);
cnt[x]++;
if (cnt[x]==1){
if (s0==-1){
s0 = e0 = x;
val = 0;
}
else{
int prv = prf.query(1, dfn[x]-1);
int nxt = suf.query(dfn[x]+1, n);
// printf(" ok %d %d\n", prv, nxt);
if (prv==-INF) prv = e0;
else prv = INV[prv];
if (nxt==INF) nxt = s0;
else nxt = INV[nxt];
val -= dist(prv, nxt);
val += dist(prv, x);
val += dist(x, nxt);
if (dfn[e0] < dfn[x]) e0 = x;
if (dfn[x] < dfn[s0]) s0 = x;
// printf("prv = %d / nxt = %d / range: [%d, %d] / val = %d\n", prv, nxt, s0, e0, val);
}
prf.update(dfn[x], dfn[x]);
suf.update(dfn[x], dfn[x]);
// 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){
if (s0==e0){
s0 = e0 = -1;
val = 0;
}
else{
int prv = prf.query(1, dfn[x]-1);
int nxt = suf.query(dfn[x]+1, n);
if (prv==-INF) prv = e0;
else prv = INV[prv];
if (nxt==INF) nxt = s0;
else nxt = INV[nxt];
val += dist(prv, nxt);
val -= dist(prv, x);
val -= dist(x, nxt);
if (e0==x) e0 = prv;
if (s0==x) s0 = nxt;
// printf("prv = %d / nxt = %d / range: [%d, %d] / val = %d\n", prv, nxt, s0, e0, val);
}
prf.update(dfn[x], -INF);
suf.update(dfn[x], INF);
// 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 main(){
int 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;
s0 = e0 = -1;
prf.init(n+1);
suf.init(n+1);
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/2 + 1;
}
for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:238:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
238 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:242:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
242 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:247:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
247 | for (int i=1;i<=m;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
tourism.cpp:250:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
250 | scanf("%d %d", &Q[i].s, &Q[i].e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5844 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 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 |
5844 KB |
Output is correct |
9 |
Correct |
6 ms |
5860 KB |
Output is correct |
10 |
Correct |
5 ms |
5844 KB |
Output is correct |
11 |
Correct |
5 ms |
5860 KB |
Output is correct |
12 |
Correct |
3 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 |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
4 ms |
5864 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
22 |
Correct |
4 ms |
5860 KB |
Output is correct |
23 |
Correct |
6 ms |
5860 KB |
Output is correct |
24 |
Correct |
4 ms |
5844 KB |
Output is correct |
25 |
Correct |
5 ms |
5844 KB |
Output is correct |
26 |
Correct |
4 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
2 ms |
5844 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5844 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 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 |
5844 KB |
Output is correct |
9 |
Correct |
6 ms |
5860 KB |
Output is correct |
10 |
Correct |
5 ms |
5844 KB |
Output is correct |
11 |
Correct |
5 ms |
5860 KB |
Output is correct |
12 |
Correct |
3 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 |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
4 ms |
5864 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
22 |
Correct |
4 ms |
5860 KB |
Output is correct |
23 |
Correct |
6 ms |
5860 KB |
Output is correct |
24 |
Correct |
4 ms |
5844 KB |
Output is correct |
25 |
Correct |
5 ms |
5844 KB |
Output is correct |
26 |
Correct |
4 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
2 ms |
5844 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
30 |
Correct |
32 ms |
5944 KB |
Output is correct |
31 |
Correct |
37 ms |
5844 KB |
Output is correct |
32 |
Correct |
45 ms |
5996 KB |
Output is correct |
33 |
Correct |
54 ms |
6004 KB |
Output is correct |
34 |
Correct |
44 ms |
6004 KB |
Output is correct |
35 |
Correct |
5 ms |
5972 KB |
Output is correct |
36 |
Correct |
5 ms |
6028 KB |
Output is correct |
37 |
Correct |
5 ms |
5972 KB |
Output is correct |
38 |
Correct |
39 ms |
6104 KB |
Output is correct |
39 |
Correct |
37 ms |
6112 KB |
Output is correct |
40 |
Correct |
44 ms |
6120 KB |
Output is correct |
41 |
Correct |
7 ms |
6100 KB |
Output is correct |
42 |
Correct |
5 ms |
6100 KB |
Output is correct |
43 |
Correct |
6 ms |
6100 KB |
Output is correct |
44 |
Correct |
39 ms |
6044 KB |
Output is correct |
45 |
Correct |
38 ms |
6032 KB |
Output is correct |
46 |
Correct |
39 ms |
6052 KB |
Output is correct |
47 |
Correct |
4 ms |
5972 KB |
Output is correct |
48 |
Correct |
5 ms |
6024 KB |
Output is correct |
49 |
Correct |
5 ms |
5972 KB |
Output is correct |
50 |
Correct |
40 ms |
5972 KB |
Output is correct |
51 |
Correct |
37 ms |
5972 KB |
Output is correct |
52 |
Correct |
38 ms |
6000 KB |
Output is correct |
53 |
Correct |
40 ms |
6000 KB |
Output is correct |
54 |
Correct |
40 ms |
5972 KB |
Output is correct |
55 |
Correct |
39 ms |
5972 KB |
Output is correct |
56 |
Correct |
4 ms |
5844 KB |
Output is correct |
57 |
Correct |
4 ms |
5944 KB |
Output is correct |
58 |
Correct |
6 ms |
5972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 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 |
Correct |
4089 ms |
15812 KB |
Output is correct |
5 |
Correct |
3517 ms |
19140 KB |
Output is correct |
6 |
Correct |
4369 ms |
20544 KB |
Output is correct |
7 |
Execution timed out |
5087 ms |
22112 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5844 KB |
Output is correct |
2 |
Correct |
160 ms |
9752 KB |
Output is correct |
3 |
Correct |
244 ms |
10216 KB |
Output is correct |
4 |
Correct |
192 ms |
10668 KB |
Output is correct |
5 |
Correct |
72 ms |
12840 KB |
Output is correct |
6 |
Correct |
88 ms |
12948 KB |
Output is correct |
7 |
Correct |
132 ms |
12944 KB |
Output is correct |
8 |
Correct |
139 ms |
12900 KB |
Output is correct |
9 |
Correct |
165 ms |
12840 KB |
Output is correct |
10 |
Correct |
188 ms |
12944 KB |
Output is correct |
11 |
Correct |
276 ms |
12852 KB |
Output is correct |
12 |
Correct |
333 ms |
12984 KB |
Output is correct |
13 |
Correct |
319 ms |
13024 KB |
Output is correct |
14 |
Correct |
347 ms |
13556 KB |
Output is correct |
15 |
Correct |
319 ms |
14656 KB |
Output is correct |
16 |
Correct |
258 ms |
13060 KB |
Output is correct |
17 |
Correct |
233 ms |
13088 KB |
Output is correct |
18 |
Correct |
243 ms |
13068 KB |
Output is correct |
19 |
Correct |
63 ms |
13004 KB |
Output is correct |
20 |
Correct |
86 ms |
12876 KB |
Output is correct |
21 |
Correct |
92 ms |
12952 KB |
Output is correct |
22 |
Correct |
120 ms |
12988 KB |
Output is correct |
23 |
Correct |
115 ms |
12932 KB |
Output is correct |
24 |
Correct |
130 ms |
12972 KB |
Output is correct |
25 |
Correct |
151 ms |
12956 KB |
Output is correct |
26 |
Correct |
144 ms |
12948 KB |
Output is correct |
27 |
Correct |
207 ms |
12996 KB |
Output is correct |
28 |
Correct |
248 ms |
12964 KB |
Output is correct |
29 |
Correct |
264 ms |
13004 KB |
Output is correct |
30 |
Correct |
282 ms |
13012 KB |
Output is correct |
31 |
Correct |
311 ms |
13332 KB |
Output is correct |
32 |
Correct |
293 ms |
13312 KB |
Output is correct |
33 |
Correct |
310 ms |
13780 KB |
Output is correct |
34 |
Correct |
288 ms |
14752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5844 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Execution timed out |
5047 ms |
11280 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5716 KB |
Output is correct |
2 |
Correct |
2 ms |
5844 KB |
Output is correct |
3 |
Correct |
2 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 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 |
5844 KB |
Output is correct |
9 |
Correct |
6 ms |
5860 KB |
Output is correct |
10 |
Correct |
5 ms |
5844 KB |
Output is correct |
11 |
Correct |
5 ms |
5860 KB |
Output is correct |
12 |
Correct |
3 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 |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
4 ms |
5864 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
22 |
Correct |
4 ms |
5860 KB |
Output is correct |
23 |
Correct |
6 ms |
5860 KB |
Output is correct |
24 |
Correct |
4 ms |
5844 KB |
Output is correct |
25 |
Correct |
5 ms |
5844 KB |
Output is correct |
26 |
Correct |
4 ms |
5844 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
2 ms |
5844 KB |
Output is correct |
29 |
Correct |
3 ms |
5844 KB |
Output is correct |
30 |
Correct |
32 ms |
5944 KB |
Output is correct |
31 |
Correct |
37 ms |
5844 KB |
Output is correct |
32 |
Correct |
45 ms |
5996 KB |
Output is correct |
33 |
Correct |
54 ms |
6004 KB |
Output is correct |
34 |
Correct |
44 ms |
6004 KB |
Output is correct |
35 |
Correct |
5 ms |
5972 KB |
Output is correct |
36 |
Correct |
5 ms |
6028 KB |
Output is correct |
37 |
Correct |
5 ms |
5972 KB |
Output is correct |
38 |
Correct |
39 ms |
6104 KB |
Output is correct |
39 |
Correct |
37 ms |
6112 KB |
Output is correct |
40 |
Correct |
44 ms |
6120 KB |
Output is correct |
41 |
Correct |
7 ms |
6100 KB |
Output is correct |
42 |
Correct |
5 ms |
6100 KB |
Output is correct |
43 |
Correct |
6 ms |
6100 KB |
Output is correct |
44 |
Correct |
39 ms |
6044 KB |
Output is correct |
45 |
Correct |
38 ms |
6032 KB |
Output is correct |
46 |
Correct |
39 ms |
6052 KB |
Output is correct |
47 |
Correct |
4 ms |
5972 KB |
Output is correct |
48 |
Correct |
5 ms |
6024 KB |
Output is correct |
49 |
Correct |
5 ms |
5972 KB |
Output is correct |
50 |
Correct |
40 ms |
5972 KB |
Output is correct |
51 |
Correct |
37 ms |
5972 KB |
Output is correct |
52 |
Correct |
38 ms |
6000 KB |
Output is correct |
53 |
Correct |
40 ms |
6000 KB |
Output is correct |
54 |
Correct |
40 ms |
5972 KB |
Output is correct |
55 |
Correct |
39 ms |
5972 KB |
Output is correct |
56 |
Correct |
4 ms |
5844 KB |
Output is correct |
57 |
Correct |
4 ms |
5944 KB |
Output is correct |
58 |
Correct |
6 ms |
5972 KB |
Output is correct |
59 |
Correct |
3 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 |
Correct |
4089 ms |
15812 KB |
Output is correct |
63 |
Correct |
3517 ms |
19140 KB |
Output is correct |
64 |
Correct |
4369 ms |
20544 KB |
Output is correct |
65 |
Execution timed out |
5087 ms |
22112 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |