Submission #801954

#	Time	Username	Problem	Language	Result	Execution time	Memory
801954		Soumya1	Valley (BOI19_valley)	C++17	100 / 100	187 ms	42812 KiB

valley

#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 1e5 + 5;
const int lg = 20;
const long long inf = 1e18;
vector<tuple<int, int, int>> ad[mxN];
bool on[mxN];
int lower[mxN], level[mxN], in[mxN], out[mxN], timer, par[mxN][lg];
long long dist[mxN], depth[mxN];
long long st[mxN][lg];
void dfs(int u, int p) {
  in[u] = ++timer;
  if (on[u]) dist[u] = 0;
  par[u][0] = p;
  for (auto [v, w, i] : ad[u]) {
    if (v == p) continue;
    lower[i] = v;
    depth[v] = depth[u] + w;
    level[v] = level[u] + 1;
    dfs(v, u);
    dist[u] = min(dist[u], dist[v] + w);
  }
  out[u] = timer;
}
void build_ST_dfs(int u, int p) {
  st[u][0] = (dist[u] == inf ? inf : dist[u] - depth[u]);
  for (int i = 1; i < lg; i++) {
    par[u][i] = par[par[u][i - 1]][i - 1];
    st[u][i] = min(st[u][i - 1], st[par[u][i - 1]][i - 1]);
  }
  for (auto [v, w, i] : ad[u]) {
    if (v == p) continue;
    build_ST_dfs(v, u);
  }
}
void testCase() {
  int n, s, q, e;
  cin >> n >> s >> q >> e;
  for (int i = 1; i <= n; i++) {
    dist[i] = inf;
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    ad[u].push_back({v, w, i + 1});
    ad[v].push_back({u, w, i + 1});
  }
  for (int i = 0; i < s; i++) {
    int u;
    cin >> u;
    on[u] = 1;
  }
  dfs(e, e);
  build_ST_dfs(e, e);
  while (q--) {
    int i, r;
    cin >> i >> r;
    int t = lower[i];
    if (in[t] <= in[r] && out[r] <= out[t]) {
      long long ans = inf;
      int k = level[r] - level[t] + 1;
      int init_r = r;
      for (int i = lg - 1; i >= 0; i--) {
        if (k >> i & 1) ans = min(ans, st[r][i]), r = par[r][i];
      }
      if (ans == inf) cout << "oo\n";
      else cout << ans + depth[init_r] << "\n";
    } else {
      cout << "escaped\n";
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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