Submission #530084

#	Time	Username	Problem	Language	Result	Execution time	Memory
530084		Alex_tz307	Valley (BOI19_valley)	C++17	100 / 100	217 ms	37564 KiB

valley

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int kLog = 16;
const int64_t INF = 1e18L;
vector<tuple<int, int, int>> g[1 + kN];
int s[kN], node[kN], depth[1 + kN], anc[1 + kN][1 + kLog];
int64_t dp[1 + kN], bst[1 + kN], best[1 + kN][1 + kLog];

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}

void dfs(int u) {
  for (int i = 1; i <= kLog; ++i) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
    if (anc[u][i] == 0) {
      break;
    }
  }
  bst[u] = INF;
  for (auto it : g[u]) {
    int v, w, index;
    tie(v, w, index) = it;
    if (v != anc[u][0]) {
      node[index] = v;
      depth[v] = depth[u] + 1;
      dp[v] = dp[u] + w;
      anc[v][0] = u;
      dfs(v);
    }
  }
}

int64_t lift(int &v, int level) {
  int64_t ans = bst[v];
  for (int i = kLog; i >= 0; --i) {
    if (depth[v] - (1 << i) >= level) {
      minSelf(ans, best[v][i]);
      v = anc[v][i];
    }
  }
  return ans;
}

void testCase() {
  int n, m, q, root;
  cin >> n >> m >> q >> root;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w, i);
    g[v].emplace_back(u, w, i);
  }
  for (int i = 0; i < m; ++i) {
    cin >> s[i];
  }
  dfs(root);
  sort(s, s + m, [&](const int &u, const int &v) -> bool {
    return dp[u] < dp[v];
  });
  for (int i = 0; i < m; ++i) {
    int v = s[i];
    while (v) {
      if (bst[v] != INF) {
        break;
     }
      bst[v] = dp[s[i]] - 2 * dp[v];
      v = anc[v][0];
    }
  }
  for (int v = 1; v <= n; ++v) {
    best[v][0] = bst[anc[v][0]];
  }
  for (int j = 1; j <= kLog; ++j) {
    for (int i = 1; i <= n; ++i) {
      best[i][j] = min(best[i][j - 1], best[anc[i][j - 1]][j - 1]);
    }
  }
  for (int i = 0; i < q; ++i) {
    int index, v;
    cin >> index >> v;
    int u = v;
    lift(u, depth[node[index]]);
    if (u != node[index]) {
      cout << "escaped\n";
      continue;
    }
    int64_t ans = dp[v] + lift(v, depth[node[index]]);
    if (ans >= INF) {
      cout << "oo\n";
    } else {
      cout << ans << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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