Submission #1042823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042823		avighna	Valley (BOI19_valley)	C++17	100 / 100	167 ms	64208 KiB

valley

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

struct Edge {
  ll u, v, w;
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, s, q, e;
  std::cin >> n >> s >> q >> e;
  std::vector<std::vector<std::pair<ll, ll>>> adj(n + 1);
  std::vector<Edge> edges;
  for (ll i = 0, u, v, w; i < n - 1; ++i) {
    std::cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    edges.push_back({u, v, w});
  }

  std::vector<ll> d(n + 1), depth(n + 1);
  std::function<void(ll, ll)> dfs;
  std::vector<ll> start(n + 1), end(n + 1);
  ll timer = 0;
  std::vector<std::vector<ll>> lift(n + 1, std::vector<ll>(20));
  dfs = [&](ll node, ll par) {
    start[node] = timer++;
    for (auto &[i, wt] : adj[node]) {
      if (i == par) {
        continue;
      }
      lift[i][0] = node;
      d[i] = d[node] + wt;
      depth[i] = depth[node] + 1;
      dfs(i, node);
    }
    end[node] = timer - 1;
  };
  lift[e][0] = e;
  dfs(e, 0);

  std::vector<bool> shop(n + 1);
  for (ll i = 0, v; i < s; ++i) {
    std::cin >> v;
    shop[v] = true;
  }

  // dp[i] = - 2 * d[i] + min{d[x] forall shop[x] == true, x is in the subtree
  // of i}
  std::vector<ll> dp(n + 1);
  std::function<void(ll, ll)> dfs2;
  dfs2 = [&](ll node, ll par) {
    if (shop[node]) {
      dp[node] = d[node];
    } else {
      dp[node] = inf;
    }
    for (auto &[i, wt] : adj[node]) {
      if (i == par) {
        continue;
      }
      dfs2(i, node);
      dp[node] = std::min(dp[node], dp[i]);
    }
  };
  dfs2(e, 0);
  for (ll i = 1; i <= n; ++i) {
    if (dp[i] != inf) {
      dp[i] -= 2 * d[i];
    }
  }

  std::vector<std::vector<ll>> lmin(n + 1, std::vector<ll>(20));
  for (ll i = 1; i <= n; ++i) {
    lmin[i][0] = dp[i];
  }
  for (ll bt = 1; bt < 20; ++bt) {
    for (ll i = 1; i <= n; ++i) {
      lmin[i][bt] = std::min(lmin[i][bt - 1], lmin[lift[i][bt - 1]][bt - 1]);
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
    }
  }

  auto binary_lift = [&](ll x, ll c) {
    ll ans = inf;
    for (ll bt = 0; bt < 20; ++bt) {
      if (c & (1 << bt)) {
        ans = std::min(ans, lmin[x][bt]);
        x = lift[x][bt];
      }
    }
    return ans;
  };

  while (q--) {
    ll i, r;
    std::cin >> i >> r;
    --i;
    auto [u, v, wt] = edges[i];
    if (d[u] > d[v]) {
      std::swap(u, v);
    }
    if (!(start[v] <= start[r] and start[r] <= end[v])) {
      std::cout << "escaped\n";
      continue;
    }
    ll val = binary_lift(r, depth[r] - depth[v] + 1);
    if (val == inf) {
      std::cout << "oo\n";
    } else {
      std::cout << val + d[r] << '\n';
    }
  }
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41