Submission #922948

#	Time	Username	Problem	Language	Result	Execution time	Memory
922948		lto5	Valley (BOI19_valley)	C++17	100 / 100	147 ms	43860 KiB

valley

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int LG = __lg(N) + 5;

int n, s, q, e;
int a[N], b[N], w[N];
vector<int> g[N];
int marked[N];

int tin[N];
int tout[N];
int time_dfs;
int h[N];
int64_t d[N];
int f[N][LG];
int64_t min_d[N][LG];

void dfs(int u) {
  tin[u] = ++time_dfs;
  if (marked[u]) {
    min_d[u][0] = d[u];
  }
  else {
    min_d[u][0] = 9e18;
  }
  for (int edge : g[u]) {
    int v = a[edge] ^ b[edge] ^ u;
    if (v == f[u][0]) {
      continue;
    }
    h[v] = h[u] + 1;
    d[v] = d[u] + w[edge];
    f[v][0] = u;
    dfs(v);
    min_d[u][0] = min(min_d[u][0], min_d[v][0]);
  }
  tout[u] = time_dfs;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  #define task "valley"
  if (fopen(task".inp", "r")) {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
  }
  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; i++) {
    cin >> a[i] >> b[i] >> w[i];
    g[a[i]].emplace_back(i);
    g[b[i]].emplace_back(i);
  }
  while (s--) {
    int u;
    cin >> u;
    marked[u] = 1;
  }
  memset(min_d, 0x3f, sizeof(min_d));
  const int64_t inf = min_d[0][0];
  h[e] = 1;
  dfs(e);
  for (int u = 1; u <= n; u++) {
    if (min_d[u][0] != inf)
      min_d[u][0] -= 2 * d[u];
  }
  for (int i = 0; i + 1 < LG; i++) {
    for (int u = 1; u <= n; u++) {
      f[u][i + 1] = f[f[u][i]][i];
      min_d[u][i + 1] = min(min_d[u][i], min_d[f[u][i]][i]);
    }
  }
  for (int i = 1; i < n; i++) {
    if (h[a[i]] > h[b[i]]) {
      swap(a[i], b[i]);
    }
  }
  while (q--) {
    int e, u;
    cin >> e >> u;
    if (tin[b[e]] <= tin[u] && tin[u] <= tout[b[e]]) {
      int dif = h[u] - h[b[e]];
      int64_t best = inf;
      int v = u;
      for (int k = LG - 1; k >= 0; k--) {
        if (dif >> k & 1) {
          best = min(best, min_d[v][k]);
          v = f[v][k];
        }
      }
      best = min(best, min_d[v][0]);
      if (best == inf) {
        cout << "oo\n";
      }
      else {
        cout << best + d[u] << "\n";
      }
    }
    else {
      cout << "escaped\n";
    }
  }
  return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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