Submission #1004023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004023		May27_th	Valley (BOI19_valley)	C++17	100 / 100	141 ms	44532 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const i64 INF = 1e18;
const int MAXN = 100015;
int villages, shops, Q, exitP, h[MAXN], up[MAXN][22];
int counter = 0, tin[MAXN], tout[MAXN];
i64 d[MAXN], mind[MAXN], upd[MAXN][22];
bool isShop[MAXN];
pair<int, int> Edges[MAXN];
vector<pair<int, int>> G[MAXN];
void dfs(int u) {
  tin[u] = tout[u] = ++counter;
  if (isShop[u]) mind[u] = d[u];
  else mind[u] = INF;
  for (auto [v, w] : G[u]) {
    if (v != up[u][0]) {
      up[v][0] = u;
      d[v] = d[u] + w;
      h[v] = h[u] + 1;
      for (int j = 1; j <= 20; j ++) {
        up[v][j] = up[up[v][j - 1]][j - 1];
      }
      dfs(v);
      mind[u] = min(mind[u], mind[v]);
    }
  }
  tout[u] = counter;
}
void dfs1(int u) {
  for (auto [v, w] : G[u]) {
    if (v != up[u][0]) {
      upd[v][0] = mind[u];
      for (int j = 1; j <= 20; j ++) {
        upd[v][j] = min(upd[v][j - 1], upd[up[v][j - 1]][j - 1]);
      }
      dfs1(v);
    }
  }
}
void Solve (void) {
  cin >> villages >> shops >> Q >> exitP;
  for (int i = 1; i <= villages; i ++) isShop[i] = false;
  for (int i = 1; i < villages; i ++) {
    int u, v, w; cin >> u >> v >> w;
    G[u].pb(mp(v, w));
    G[v].pb(mp(u, w));
    Edges[i] = mp(u, v);
  }
  for (int i = 1; i <= shops; i ++) {
    int x; cin >> x;
    isShop[x] = true;
  }
  dfs(exitP);
  for (int i = 1; i <= villages; i ++) {
    if (mind[i] != INF) mind[i] = mind[i] - 2 * d[i];
  }
  dfs1(exitP);
  while (Q --) {
    int RoadID, st; cin >> RoadID >> st;
    auto [u, v] = Edges[RoadID];
    if (h[v] < h[u]) swap(u, v);
    if (tin[v] <= tin[st] && tout[st] <= tout[v]) {
      // Lie in subtree
      int gap = h[st] - h[v];
      i64 mn = mind[st], add = d[st];
      for (int j = 20; j >= 0; j --) {
        if (gap >> j & 1) {
          mn = min(mn, upd[st][j]);
          st = up[st][j];
        }
      }
      if (mn >= INF) cout << "oo" << "\n";
      else cout << mn + add << "\n";
    } else {
      cout << "escaped" << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  // Prepare();
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    Solve();
  }
}

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