Submission #1221797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221797		noyancanturk	Tourism (JOI23_tourism)	C++20	28 / 100	5095 ms	30792 KiB

tourism

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

vector<int>v[lim];
int c[lim];
int l[lim],r[lim];
int p[lim];
int anss[lim];
int dep[lim];
int tin[lim],tour[lim],tt=1;
int lg[lim];

void dfs(int node,int par){
  tin[node]=tt;
  tour[tt++]=tin[node];
  dep[tin[node]]=dep[tin[par]]+1;
  for(int j:v[node]){
    if(j==par)continue;
    dfs(j,node);
    tour[tt++]=tin[node];
  }
}

int table[20][lim];

int lca(int i,int j){
  if(j<i)swap(i,j);
  int ll=lg[j-i+1];
  return min(table[ll][i],table[ll][j-(1<<ll)+1]);
}

int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m,q;
  cin>>n>>m>>q;
  for(int i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
  }
  dfs(1,0);
  for(int i=0;i<lim;i++){
    if(1<i)lg[i]=lg[i/2]+1;
    table[0][i]=tour[i];
  }
  for(int i=1;i<20;i++){
    for(int j=0;j<lim;j++){
      if(lim<=j+(1<<i))break;
      table[i][j]=min(table[i-1][j],table[i-1][j+(1<<(i-1))]);
    }
  }
  for(int i=0;i<m;i++){
    cin>>c[i];
    c[i]=tin[c[i]];
  }
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    l[i]--,r[i]--;
    p[i]=i;
  }
  sort(p,p+q,[&](int i,int j)->bool {
    if(l[i]/500!=l[j]/500)return l[i]<l[j];
    return r[i]<r[j];
  });
  int L=-1,R=-1;
  int ans=0;
  multiset<int>st;
  for(int i=0;i<q;i++){
    int ll=l[p[i]],rr=r[p[i]];
    if(L==-1){
      L=R=ll;
      st.insert(c[ll]);
      ans+=dep[c[ll]];
    }
    while(ll<L){
      L--;
      int g=c[L];
      ans+=dep[g];
      auto p=st.lower_bound(g);
      if(p!=st.begin()){
        auto pp=prev(p);
        ans-=dep[lca(*pp,g)];
        if(p!=st.end()){
          ans+=dep[lca(*pp,*p)];
        }
      }
      if(p!=st.end()){
        ans-=dep[lca(g,*p)];
      }
      st.insert(g);
    }
    while(R<rr){
      R++;
      int g=c[R];
      ans+=dep[g];
      auto p=st.lower_bound(g);
      if(p!=st.begin()){
        auto pp=prev(p);
        ans-=dep[lca(*pp,g)];
        if(p!=st.end()){
          ans+=dep[lca(*pp,*p)];
        }
      }
      if(p!=st.end()){
        ans-=dep[lca(g,*p)];
      }
      st.insert(g);
    }
    while(L<ll){
      int g=c[L];
      ans-=dep[g];
      st.erase(st.find(g));
      auto p=st.lower_bound(g);
      if(p!=st.begin()){
        auto pp=prev(p);
        ans+=dep[lca(*pp,g)];
        if(p!=st.end()){
          ans-=dep[lca(*pp,*p)];
        }
      }
      if(p!=st.end()){
        ans+=dep[lca(g,*p)];
      }
      L++;
    }
    while(rr<R){
      int g=c[R];
      ans-=dep[g];
      st.erase(st.find(g));
      auto p=st.lower_bound(g);
      if(p!=st.begin()){
        auto pp=prev(p);
        ans+=dep[lca(*pp,g)];
        if(p!=st.end()){
          ans-=dep[lca(*pp,*p)];
        }
      }
      if(p!=st.end()){
        ans+=dep[lca(g,*p)];
      }
      R--;
    }
    anss[p[i]]=ans-dep[lca(*st.begin(),*st.rbegin())]+1;
  }
  for(int i=0;i<q;i++){
    cout<<anss[i]<<'\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41