Submission #850625

#	Time	Username	Problem	Language	Result	Execution time	Memory
850625		huutuan	Tourism (JOI23_tourism)	C++14	28 / 100	5094 ms	76356 KiB

tourism

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=1e5+1, S=320, LG=18;

struct query{
   int l, r, i;

   query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}

   bool operator<(const query& x){
      return l/S!=x.l/S?l<x.l:r<x.r;
   }
} qq[N];

int n, m, q, a[N], tdfs, tin[N], tout[N], dep[N], ans[N];
pair<int, int> st[N*2][LG];
vector<int> g[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   dep[u]=dep[p]+1;
   st[tdfs][0]={dep[u], u};
   for (int v:g[u]) if (v!=p){
      dfs(v, u);
      ++tdfs;
      st[tdfs][0]={dep[u], u};
   }
   tout[u]=tdfs;
}

void build(){
   for (int k=1; k<LG; ++k) for (int i=1; i+(1<<k)-1<=tdfs; ++i) st[i][k]=min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
}

int lca(int u, int v){
   u=tin[u]; v=tin[v];
   if (u>v) swap(u, v);
   int lg=__lg(v-u+1);
   return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> m >> q;
   for (int i=1; i<n; ++i){
      int x, y; cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
   dfs(1, 0);
   build();
   for (int i=1; i<=m; ++i) cin >> a[i];
   for (int i=1; i<=q; ++i){
      int x, y; cin >> x >> y;
      qq[i]={x, y, i};
   }
   sort(qq+1, qq+q+1);
   multiset<pair<int, int>> st;
   int val=0;
   function<int(int, int)> calc=[&](int x, int y) -> int {
      return dep[y]-dep[lca(x, y)];
   };
   function<void(int)> add=[&](int x) -> void {
      if (st.empty()){
         st.emplace(tin[x], x);
         return;
      }
      auto it=st.lower_bound({tin[x], x});
      auto previt=it==st.begin()?prev(st.end()):prev(it);
      auto nextit=it==st.end()?st.begin():it;
      val-=calc(previt->second, nextit->second);
      val+=calc(previt->second, x);
      val+=calc(x, nextit->second);
      st.emplace(tin[x], x);
   };
   function<void(int)> del=[&](int x) -> void {
      if (sz(st)==1){
         st.erase({tin[x], x});
         return;
      }
      auto it=st.find({tin[x], x});
      auto previt=it==st.begin()?prev(st.end()):prev(it);
      auto nextit=it==prev(st.end())?st.begin():next(it);
      val+=calc(previt->second, nextit->second);
      val-=calc(previt->second, x);
      val-=calc(x, nextit->second);
      st.erase(it);
   };
   int cl=1, cr=0;
   for (int i=1; i<=q; ++i){
      int l=qq[i].l, r=qq[i].r;
      while (l<cl){
         --cl;
         add(a[cl]);
      }
      while (r>cr){
         ++cr;
         add(a[cr]);
      }
      while (l>cl){
         del(a[cl]);
         ++cl;
      }
      while (r<cr){
         del(a[cr]);
         --cr;
      }
      ans[qq[i].i]=val;
   }
   for (int i=1; i<=q; ++i) cout << ans[i]+1 << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   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