Submission #1092796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092796		juicy	Valley (BOI19_valley)	C++17	100 / 100	110 ms	37716 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17;
const long long inf = 1e18;

int n, k, q, rt;
int pr[LG][N], h[N], ver[N], w[N];
bool shop[N];
long long dep[N], a[LG][N], best[N];
vector<array<int, 2>> g[N];

bool check(int p, int u) {
  for (int i = LG - 1; ~i; --i) {
    if (h[u] - (1 << i) >= h[p]) {
      u = pr[i][u];
    }
  }
  return u == p;
}

void dfs(int u) {
  for (auto [v, id] : g[u]) {
    if (v ^ pr[0][u]) {
      ver[id] = v;
      pr[0][v] = u;
      dep[v] = dep[u] + w[id];
      h[v] = h[u] + 1;
      dfs(v);
      best[u] = min(best[u], best[v]);
    }
  }
  best[u] = min(best[u], shop[u] ? dep[u] : inf);
  a[0][u] = best[u] == inf ? inf : best[u] - 2 * dep[u];
}

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

  cin >> n >> k >> q >> rt;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v >> w[i];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  while (k--) {
    int u; cin >> u;
    shop[u] = 1;
  }
  memset(best, 0x3f, sizeof(best));
  dfs(rt);
  for (int i = 1; i < LG; ++i) {
    for (int u = 1; u <= n; ++u) {
      a[i][u] = min(a[i - 1][u], a[i - 1][pr[i - 1][u]]);
      pr[i][u] = pr[i - 1][pr[i - 1][u]];
    }
  }
  while (q--) {
    int i, r; cin >> i >> r;
    i = ver[i];
    if (check(i, r)) {
      long long x = inf;
      int u = r;
      for (int j = LG - 1; ~j; --j) {
        if (h[r] - (1 << j) >= h[i] - 1) {
          x = min(x, a[j][r]);
          r = pr[j][r];
        }
      }
      if (x != inf) {
        cout << x + dep[u] << "\n";
      } else {
        cout << "oo" << "\n";
      }
    } else {
      cout << "escaped" << "\n";
    }
  }
  return 0;
}

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