Submission #1164929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164929		fryingduc	Valley (BOI19_valley)	C++20	100 / 100	169 ms	37236 KiB

valley

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int LG = 18;
int n, s, q, e;
int eu[maxn], ev[maxn], ew[maxn];
vector<pair<int, int>> g[maxn];
bool spec[maxn];
int up[maxn][LG + 1], h[maxn];
long long st[maxn][LG + 1];
long long dep[maxn];
long long f[maxn];

void pre_dfs(int u, int prev) {
  f[u] = 1e18;
  if (spec[u]) f[u] = 0;
  for (auto [v, w] : g[u]) {
    if (v == prev) continue;
    up[v][0] = u;
    for (int i = 1; i <= LG; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    h[v] = h[u] + 1;
    dep[v] = dep[u] + w;
    pre_dfs(v, u);
    if (f[u] > f[v] + w) {
      f[u] = f[v] + w;
    }
  }
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG; i >= 0; --i) {
    if ((h[u] - h[v]) >> i & 1) u = up[u][i];
  }
  if (u == v) return u;
  for (int i = LG; i >= 0; --i) {
    if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
  }
  return up[v][0];
}

long long dist(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void solve() {
  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; ++i) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    eu[i] = u, ev[i] = v, ew[i] = w;
  }
  for (int i = 1; i <= s; ++i) {
    int x; cin >> x;
    spec[x] = 1;
  }
  pre_dfs(e, 0);
  for (int i = 1; i <= n; ++i) {
    st[i][0] = f[up[i][0]] - dep[up[i][0]];
  }
  for (int i = 1; i <= LG; ++i) {
    for (int u = 1; u <= n; ++u) {
      st[u][i] = min(st[u][i - 1], st[up[u][i - 1]][i - 1]);
    }
  }
  while (q--) {
    int edge, r; cin >> edge >> r;
    int pu = eu[edge], pv = ev[edge];
    if (up[pu][0] == pv) swap(pu, pv);
    if (lca(r, pv) != pv) {
      cout << "escaped\n";
      continue;
    }
    int u = r;
    long long res = f[u];
    for (int i = LG; i >= 0; --i) {
      if ((h[u] - h[pv]) >> i & 1) {
        res = min(res, dep[r] + st[u][i]);
        u = up[u][i];
      }
    }
    if (res == 1e18) {
      cout << "oo\n";
    } else cout << res << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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