제출 #1220335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220335		Younis_Dwai	Tourism (JOI23_tourism)	C++20	28 / 100	5093 ms	18884 KiB

tourism

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
//#define int long long
#define F first
#define S second
#define pb push_back
#define popp pop_back
//#define in insert
#define endl "\n"
#define mid (l+r)/2
using namespace std;
const int N=2e5+5;
int n,m,QQ,C[N],bit[N],depth[N],nxt[N][21],in[N],out[N],tt=0;
vector<int> adj[N];
void upd(int id , int v){
     while(id<=tt){
           bit[id]+=v;
           id+=(id&(-id));
     }
     return ;
}
int S(int id){
    int ret=0;
    while(id){
          ret+=bit[id];
          id-=(id&(-id));
    }
    return ret;
}

int query(int l , int r){
    return S(r)-S(l-1);
}
void dfs(int node , int par){
     in[node]=++tt;
     nxt[node][0]=par;
     for(int i=1;i<=20;i++) nxt[node][i]=nxt[nxt[node][i-1]][i-1];
     for(auto u : adj[node]){
         if(u==par) continue ;
         depth[u]=1+depth[node];
         dfs(u,node);
     }
     out[node]=tt;
     return ;
}
int lca(int u  , int v){
    if(depth[v]>depth[u]) swap(u,v);
    for(int i=20;i>=0;i--){
        if(depth[u]-(1<<i)>=depth[v]) u=nxt[u][i];
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(nxt[u][i]!=nxt[v][i]) u=nxt[u][i],v=nxt[v][i];
    return nxt[u][0];
}
int up(int node,  int k){
    for(int i=0;i<=20;i++){
        if((k&(1<<i))) node=nxt[node][i];
    }
    return node;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>QQ;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(1,1);
    for(int i=1;i<=m;i++) cin>>C[i];
    while(QQ--){
          int l,r;cin>>l>>r;
          int root=C[l];
          for(int i=l;i<=r;i++){
              root=lca(root,C[i]);
          }
          int ret=1;
          upd(in[root],1);
          vector<int> v;
          for(int i=l;i<=r;i++){
              int node=C[i];
              if(query(in[node],out[node])) continue ;
              int ll=1,rr=n,midd=(ll+rr)/2;
              while(ll<rr){
                   int above=up(node,midd);
                   if(query(in[above],out[above])) rr=midd;
                   else ll=midd+1;
                   midd=(ll+rr)/2;
              }
              ret+=midd;
              upd(in[C[i]],1);
              v.pb(C[i]);
          }
          upd(in[root],-1);
          for(auto u : v) upd(in[u],-1);
          cout<<ret<<endl;
    }
    return 0;
}

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