| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789253 |
2023-07-21T08:39:57 Z |
박상훈(#10042) |
Tourism (JOI23_tourism) |
C++17 |
|
4 ms |
5844 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<=m;i++){
prf.update(i, a[i]);
suf.update(i, a[i]);
}
for (int i=1;i<=q;i++){
ans[Q[i].i] = prf.query(Q[i].s, Q[i].e) - suf.query(Q[i].s, Q[i].e) + 1;
}
for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
return 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/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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5844 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
