Submission #590959

#	Time	Username	Problem	Language	Result	Execution time	Memory
590959		Shin	Valley (BOI19_valley)	C++14	0 / 100	133 ms	18320 KiB

valley

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 1e5 + 7;
const int LOG = 20;

int n, num_shop, q, ec;
int dist[N];
int tin[N];
int tout[N];
bool shop[N];
int jump[N][LOG + 1];

long long dp[N];
vector<pair<int, int>> adj[N];
pair<int, int> e[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> num_shop >> q >> ec;
  for (int i = 1; i < n; i ++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
    e[i] = mp(u, v);
  }
  for (int i = 1; i <= num_shop; i ++) {
    int u; cin >> u;
    shop[u] = true;
  }
  const long long inf = 1e18 + 7;
  auto get_min = [&](int u, int v) {
    if (u == 0 || v == 0) {
      return u == 0 ? v : u;
    }
    return dp[u] < dp[v] ? u : v;
  };
  int timer = 0;
  dp[0] = inf;
  function<void(int, int)> dfs = [&](int u, int p) {
    if (shop[u]) {
      dp[u] = dist[u];
    } else {
      dp[u] = inf;
    }
    tin[u] = ++ timer;
    for (pair<int, int> v: adj[u]) if (v.fi != p) {
      dist[v.fi] = dist[u] + v.se;
      dfs(v.fi, u);
      minimize(dp[u], dp[v.fi]);
    }
    jump[u][0] = p;
    for (int i = 1; i <= LOG; i ++) {
      jump[u][i] = get_min(jump[u][i - 1], jump[jump[u][i - 1]][i - 1]);
    }
    tout[u] = timer;
  };
  auto anc = [&](int u, int v) -> bool {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
  };
  dfs(ec, ec);
  for (int i = 1; i <= n; i ++) if (dp[i] != inf) {
    dp[i] -= 2 * dist[i];
  }
  while (q --) {
    int i, u; cin >> i >> u;
    if (dist[e[i].fi] < dist[e[i].se]) {
      swap(e[i].fi, e[i].se);
    }
    int p = e[i].fi;
    if (!anc(p, u)) {
      cout << "escaped\n";
    } else {
      long long add = dist[u];
      long long res = add + dp[u];
      for (int j = LOG; j >= 0; j --) {
        int x = jump[u][j];
        if (anc(p, x)) {
          u = x;
          minimize(res, add + dp[u]);
        }
      }
      if (res >= inf) {
        cout << "oo\n";
      } else {
        cout << res << '\n';
      }
    }
  }
  return 0;
}

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