Submission #837195

#	Time	Username	Problem	Language	Result	Execution time	Memory
837195		veehz	Tourism (JOI23_tourism)	C++17	28 / 100	5054 ms	21100 KiB

tourism

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

typedef long long ll;
typedef long double ld;
#define pb push_back

int n, m, q;
vector<vector<int>> adj;
vector<int> dfsPath;
vector<int> mp;

void dfs(int u, int p) {
  dfsPath.pb(u);
  for (auto& v : adj[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
}

namespace LCA {
int l, timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int u, int p) {
  tin[u] = ++timer;
  up[u][0] = p;
  for (int i = 1; i <= l; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (auto& v : adj[u]) {
    if (v != p) dfs(v, u);
  }
  tout[u] = ++timer;
}

/// u is ancestor of v
bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}

/// returns {lca, distance}
pair<int, int> lca(int u, int v) {
  if (u == v) return {u, 0};

  int dist = 0;
  for (int i = l; i >= 0; i--) {
    if (!is_ancestor(up[u][i], v)) {
      dist += 1 << i;
      u = up[u][i];
    }
  }
  for (int i = l; i >= 0; i--) {
    if (!is_ancestor(up[v][i], u)) {
      dist += 1 << i;
      v = up[v][i];
    }
  }
  if (is_ancestor(u, v)) return {u, dist + 1};
  if (is_ancestor(v, u)) return {v, dist + 1};
  return {up[u][0], dist + 2};
}

void preprocess(int root) {
  tin.resize(n);
  tout.resize(n);
  timer = 0;
  l = ceil(log2(n));
  up.assign(n, vector<int>(l + 1));
  dfs(root, root);
}

}  // namespace LCA

int main() {
  cin >> n >> m >> q;
  adj.assign(n, {});
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].pb(b);
    adj[b].pb(a);
  }
  dfs(0, 0);
  mp.resize(n);
  for (int i = 0; i < n; i++) {
    mp[dfsPath[i]] = i;
  }
  // for (auto& x : dfsPath) cout << x << " ";
  // cout << endl;
  // for (auto& x : mp) cout << x << " ";
  // cout << endl;

  vector<int> cities(m);
  for (int i = 0; i < m; i++) cin >> cities[i], cities[i]--;

  LCA::preprocess(0);

  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    vector<int> cur(cities.begin() + l, cities.begin() + r + 1);
    sort(cur.begin(), cur.end(),
         [&](const int a, const int b) { return mp[a] < mp[b]; });
    // cout << "Distance between " << cur[0] << " and " << cur.back() << " is "
    //      << LCA::lca(cur[0], cur.back()).second << endl;
    int dist = LCA::lca(cur[0], cur.back()).second;
    for (int i = 0; i < (int)cur.size() - 1; i++) {
      // cout << "Distance between " << cur[i] << " and " << cur[i + 1] << " is "
      //      << LCA::lca(cur[i], cur[i + 1]).second << endl;
      dist += LCA::lca(cur[i], cur[i + 1]).second;
    }

    cout << dist/2 + 1 << endl;
  }
}

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