Submission #402959

#	Time	Username	Problem	Language	Result	Execution time	Memory
402959		rama_pang	Valley (BOI19_valley)	C++17	100 / 100	296 ms	46504 KiB

valley

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

using lint = long long;
const lint INF = 1e18;

const int LOG = 18;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, S, Q, E;
  cin >> N >> S >> Q >> E;
  E--;

  vector<pair<int, int>> edges;
  vector<vector<pair<int, int>>> adj(N);
  for (int i = 1; i < N; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edges.emplace_back(u, v);
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  vector<int> depth(N);
  vector<lint> dp(N, INF);
  vector<lint> dist(N, 0);
  vector<vector<int>> par(LOG, vector<int>(N, -1));
  vector<vector<lint>> lift(LOG, vector<lint>(N, INF));

  for (int i = 0; i < S; i++) {
    int x;
    cin >> x;
    dp[--x] = 0;
  }

  const auto Dfs = [&](const auto &self, int u, int p) -> void {
    par[0][u] = p;
    vector<pair<lint, int>> ls;
    ls.emplace_back(dp[u], u);
    for (auto [v, w] : adj[u]) if (v != p) {
      dist[v] = dist[u] + w;
      depth[v] = depth[u] + 1;
      self(self, v, u);
      ls.emplace_back(dp[v] + w, v);
      dp[u] = min(dp[u], dp[v] + w);
    }
    sort(begin(ls), end(ls));
    for (auto [v, w] : adj[u]) if (v != p) {
      lift[0][v] = (ls[0].second == v ? ls[1].first : ls[0].first) - dist[u];
    }
  };

  Dfs(Dfs, E, -1);
  for (int j = 1; j < LOG; j++) {
    for (int u = 0; u < N; u++) {
      par[j][u] = par[j - 1][u];
      lift[j][u] = lift[j - 1][u];
      if (par[j - 1][u] != -1) {
        par[j][u] = par[j - 1][par[j - 1][u]];
        lift[j][u] = min(lift[j][u], lift[j - 1][par[j - 1][u]]);
      }
    }
  }

  const auto IsAncestor = [&](int x, int y) -> bool { // is x ancestor of y?
    if (depth[x] > depth[y]) return false;
    int d = depth[y] - depth[x];
    for (int i = 0; i < LOG; i++) {
      if ((d >> i) & 1) {
        y = par[i][y];
      }
    }
    return x == y;
  };

  const auto GetMinCost = [&](int u, int d) -> lint {
    if (d < 0) return INF;
    lint ans = INF;
    for (int i = 0; i < LOG; i++) {
      if ((d >> i) & 1) {
        ans = min(ans, lift[i][u]);
        u = par[i][u];
      }
    }
    ans = min(ans, lift[0][u]);
    return ans;
  };

  while (Q--) {
    int i, r;
    cin >> i >> r;
    i--, r--;
    if (IsAncestor(edges[i].first, r) && IsAncestor(edges[i].second, r)) {
      int d = depth[r] - max(depth[edges[i].first], depth[edges[i].second]);
      lint ans = min(dp[r], dist[r] + GetMinCost(r, d - 1));
      if (ans > (INF / 100)) {
        cout << "oo\n";
      } else {
        cout << ans << '\n';
      }
    } else {
      cout << "escaped\n";
    }
  }
  return 0;
}

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