Submission #1107614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107614		abczz	Tourism (JOI23_tourism)	C++17	18 / 100	210 ms	54344 KiB

tourism

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define ll long long

using namespace std;

vector <ll> adj[100000];
vector <array<ll, 2>> Q[100000];
ll bl[100000][18];
ll n, m, q, a, b, cnt, sz[100000], A[100000], D[100000], G[100000], pos[100000], X[100000];
vector <ll> V[100000];

ll tot = 0;
struct BIT{
  ll st[100050];
  void build(){
    memset(st, 0, sizeof(st));
  }
  void update(ll id, ll w) {
    if (!id) return;
    tot += w;
    for (; id<100050; id+=id&-id) st[id] += w;
  }
  ll query(ll id) {
    ll ret = 0;
    for (; id; id-=id&-id) ret += st[id];
    return ret;
  }
}bit;
struct MPSegment{
  map <ll, array<ll, 2>> mp;
  vector <ll> lazy;
  void init(ll sz) {
    mp[0] = {sz-1, -1};
  }
  void update(ll id, ll l, ll r, ll w) {
    auto it = mp.lower_bound(l);
    if (it != mp.begin()) {
      it = prev(it);
      bit.update(it->second[1]+1, -(it->second[0]-(l-1)));
      mp[it->first] = {l-1, it->second[1]};
    }
    it = mp.lower_bound(l);
    while (it != mp.end()) {
      auto nx = next(it);
      if (it->first > r) break;
      if (it->second[0] <= r) {
        bit.update(it->second[1]+1, -(it->second[0]-it->first+1));
        mp.erase(it);
      }
      else {
        bit.update(it->second[1]+1, -(r+1-it->first));
        mp[r+1] = {it->second[0], it->second[1]};
        mp.erase(it);
        break;
      }
      it = nx;
    }
    mp[l] = {r, w};
    bit.update(w+1, r-l+1);
  }
}ST[100000];
ll lca(ll a, ll b) {
  if (a == -1) return b;
  else if (b == -1) return a;
  if (D[a] > D[b]) swap(a, b);
  ll db = D[b];
  for (int j=17; j>=0; --j) {
    if (db-(1LL<<j) >= D[a]) {
      db -= (1LL<<j);
      b = bl[b][j];
    }
  }
  for (int j=17; j>=0; --j) {
    if (bl[a][j] != bl[b][j]) {
      a = bl[a][j], b = bl[b][j];
    }
  }
  if (a != b) return bl[a][0];
  else return a;
}
struct LCATree{
  ll st[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = lca(A[l], A[l+1]);
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = lca(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return -1;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return lca(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}LCAST;
void dfs(ll u, ll p) {
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v == p) continue;
    D[v] = D[u] + 1;
    bl[v][0] = u;
    sz[u] += sz[v];
    dfs(v, u);
  }
}
void hld(ll u, ll p, ll k) {
  G[u] = k, pos[u] = V[k].size();
  V[k].push_back(u);
  ll mx = -1, id = -1;
  for (auto v : adj[u]) {
    if (v == p) continue;
    if (sz[v] > mx) mx = sz[v], id = v;
  }
  if (id != -1) hld(id, u, k);
  for (auto v : adj[u]) {
    if (v == p || v == id) continue;
    X[cnt+1] = u;
    hld(v, u, ++cnt);
  }
}
void jump(ll u, ll v, ll w) {
  if (G[u] == G[v]) {
    if (pos[v] == pos[u]) return;
    ST[G[u]].update(1, pos[v], pos[u], w);
    return;
  }
  ST[G[u]].update(1, 0, pos[u], w);
  jump(X[G[u]], v, w);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> q;
  bit.build();
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(0, -1);
  hld(0, -1, 0);
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  for (int i=0; i<=cnt; ++i) {
    ST[i].init(V[i].size());
  }
  vector <ll> F(q, 0);
  for (int i=0; i<m; ++i) {
    cin >> A[i];
    --A[i];
  }
  if (m > 1) LCAST.build(1, 0, m-2);
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    Q[b].push_back({a, i});
  }
  for (int i=0; i<m; ++i) {
    jump(A[i], 0, i);
    for (auto [x, y] : Q[i]) {
      if (x == i) {
        F[y] = 1;
        continue;
      }
      F[y] = tot - bit.query(x) - (m == 1 ? 0 : D[LCAST.query(1, 0, m-2, x, i-1)]);
      //cout << tot << " " << bit.query(x) << endl;
    }
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

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