Submission #1229371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229371		noyancanturk	Tourism (JOI23_tourism)	C++20	100 / 100	1631 ms	41400 KiB

tourism

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

#define pb push_back

const int lim=2e5+100;

int n,m,q;
vector<int>v[lim];
int a[lim],l[lim],r[lim],ans[lim];
vector<int>toask[lim];

int lift[20][lim];
int dep[lim];
int tin[lim],tout[lim],tr[lim],tt=1;

struct{
  int tree[lim];
  void update(int p,int val){
    while(p<lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  int query(int p){
    int ans=0;
    while(p){
      ans+=tree[p];
      p-=p&-p;
    }
    return ans;
  }
  int query(int l,int r){
    return query(r)-query(l-1);
  }
}fw;

struct{
  int tree[4*lim];
  void init(){
    for(int i=0;i<4*lim;i++)tree[i]=INT_MAX;
  }
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=min(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(1,lim,1);
  }
  int L,R;
  int query(int l,int r,int node){
    if(L<=l&&r<=R)return tree[node];
    if(r<L||R<l)return INT_MAX;
    int mid=l+r>>1,child=node<<1;
    return min(query(l,mid,child),query(mid+1,r,child|1));
  }
  int query(int l,int r){
    L=l,R=r;
    return query(1,lim,1);
  }
}st,eu,mn;

struct{
  int tree[4*lim];
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=max(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(1,lim,1);
  }
  int L,R;
  int query(int l,int r,int node){
    if(L<=l&&r<=R)return tree[node];
    if(r<L||R<l)return INT_MIN;
    int mid=l+r>>1,child=node<<1;
    return max(query(l,mid,child),query(mid+1,r,child|1));
  }
  int query(int l,int r){
    L=l,R=r;
    return query(1,lim,1);
  }
}mx;

void dfs(int node,int par){
  dep[node]=dep[par]+1;
  tin[node]=tt;
  tr[tt]=node;
  eu.update(tt++,tin[node]);
  lift[0][node]=par;
  for(int i=1;i<20;i++){
    lift[i][node]=lift[i-1][lift[i-1][node]];
  }
  for(int j:v[node]){
    if(j==par)continue;
    dfs(j,node);
    eu.update(tt++,tin[node]);
  }
  tout[node]=tt-1;
}

int main(){
  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);
  }
  for(int i=1;i<=m;i++){
    cin>>a[i];
  }
  for(int i=1;i<=q;i++){
    cin>>l[i]>>r[i];
    toask[l[i]].pb(i);
  }
  st.init();
  eu.init();
  dfs(1,0);
  for(int i=1;i<=m;i++){
    mn.update(i,tin[a[i]]);
    mx.update(i,tin[a[i]]);
  }
  for(int L=m;L;L--){
    sort(toask[L].begin(),toask[L].end());
    toask[L].resize(unique(toask[L].begin(),toask[L].end())-toask[L].begin());
    int cur=a[L];
    while(cur){
      int col=st.query(tin[cur],tout[cur]);
      int nw=cur;
      for(int j=19;0<=j;j--){
        if(lift[j][nw]&&st.query(tin[lift[j][nw]],tout[lift[j][nw]])==col){
          nw=lift[j][nw];
        }
      }
      nw=lift[0][nw];
      if(col!=INT_MAX){
        fw.update(col,dep[nw]-dep[cur]);
      }
      cur=nw;
    }
    fw.update(L,dep[a[L]]);
    st.update(tin[a[L]],L);
    for(int j:toask[L]){
      int R=r[j];
      ans[j]=fw.query(R);
      int MN=mn.query(L,R);
      int MX=mx.query(L,R);
      int lca=eu.query(MN,MX);
      ans[j]-=dep[tr[lca]]-1;
    }
  }
  for(int i=1;i<=q;i++){
    cout<<ans[i]<<'\n';
  }
}

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