Submission #790136

#	Time	Username	Problem	Language	Result	Execution time	Memory
790136		tch1cherin	Valley (BOI19_valley)	C++17	100 / 100	1659 ms	124260 KiB

valley

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 5;
const int L = __lg(N) + 2;
vector<tuple<int, int, int>> g[N];
int dp[L][N], ancestors[N][L], depth[N], edges[N][3], sz[N], cnt[N];
long long weight[L][N], dp_down[N], dp_up[N], dp_val[N], dist[N];
bool used[N], has_shop[N];
unordered_map<int, long long> min_excluding[N];
 
void build_lifting(int u = 0, int p = 0) {
  dp[0][u] = p;
  depth[u] = p == 0 ? 0 : depth[p] + 1;
  for (int i = 1; i < L; i++) {
    dp[i][u] = dp[i - 1][dp[i - 1][u]];
    weight[i][u] = weight[i - 1][u] + weight[i - 1][dp[i - 1][u]];
  }
  for (auto [i, v, w] : g[u]) {
    if (v != p) {
      weight[0][v] = w;
      build_lifting(v, u);
    }
  }
}
 
long long dis(int u, int v) {
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  long long ans = 0;
  for (int i = L - 1; i >= 0; i--) {
    if (depth[u] - (1 << i) >= depth[v]) {
      ans += weight[i][u];
      u = dp[i][u];
    }
  }
  if (u == v) {
    return ans;
  }
  for (int i = L - 1; i >= 0; i--) {
    if (dp[i][u] != dp[i][v]) {
      ans += weight[i][u] + weight[i][v];
      u = dp[i][u], v = dp[i][v];   
    }
  }
  ans += weight[0][u] + weight[0][v];
  return ans;
}
 
bool check(int a, int b, int i) {
  return min(dis(a, edges[i][0]) + dis(edges[i][1], b), dis(b, edges[i][0]) + dis(a, edges[i][1])) + edges[i][2] == dis(a, b); 
}
 
void sizes(int u, int p) {
  sz[u] = 1;
  for (auto [i, v, w] : g[u]) {
    if (v != p && !used[v]) {
      sizes(v, u);
      sz[u] += sz[v];
    }
  }
}
 
int centroid(int u, int p, int n) {
  for (auto [i, v, w] : g[u]) {
    if (v != p && !used[v] && sz[v] > n / 2) {
      return centroid(v, u, n);
    }
  }
  return u;
}
 
void DFS1(int u, int p, int c) {
  ancestors[u][cnt[u]++] = c;
  dp_down[u] = has_shop[u] ? dist[u] : LLONG_MAX;    
  for (auto [i, v, w] : g[u]) {
    if (v != p && !used[v]) {
      dist[v] = dist[u] + w;
      DFS1(v, u, c);
      dp_down[u] = min(dp_down[u], dp_down[v]); 
    }
  }
}
 
void DFS2(int u, int p, int c) {
  long long Min = LLONG_MAX, Smin = LLONG_MAX;
  for (auto [i, v, w] : g[u]) {
    if (!used[v]) {
      Smin = min(Smin, dp_down[v]);
      if (Smin < Min) {
        swap(Smin, Min);
      }
    }
  }
  for (auto [i, v, w] : g[u]) {
    if (v != p && !used[v]) {
      auto tmp1 = dp_down[u], tmp2 = dp_down[v];
      dp_down[u] = min(has_shop[u] ? dist[u] : LLONG_MAX, dp_down[v] == Min ? Smin : Min);
      dp_down[v] = min(dp_down[v], dp_down[u]);
      min_excluding[c][i] = dp_down[u];
      DFS2(v, u, c);
      dp_down[u] = tmp1;
      dp_down[v] = tmp2;
    } 
  } 
}
 
void _build_centroids(int u) {
  sizes(u, -1);
  dist[u] = 0;
  DFS1(u, -1, u);
  dp_val[u] = dp_down[u];
  dp_up[u] = has_shop[u] ? 0 : LLONG_MAX;
  DFS2(u, -1, u);
  used[u] = true;
  for (auto [i, v, w] : g[u]) {
    if (!used[v]) {
      int C = centroid(v, u, sz[v]);
      _build_centroids(C);
    }
  }
}
 
void build_centroids() {
  memset(ancestors, -1, sizeof ancestors);
  memset(used, 0, sizeof used);
  memset(cnt, 0, sizeof cnt);
  sizes(0, -1);
  _build_centroids(centroid(0, -1, sz[0]));
}
 
void solve() {
  int n, s, q, e;
  cin >> n >> s >> q >> e;
  e--;
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edges[i][0] = u, edges[i][1] = v, edges[i][2] = w;
    g[u].emplace_back(i, v, w);
    g[v].emplace_back(i, u, w);
  }
  for (int i = 0; i < s; i++) {
    int C;
    cin >> C;
    has_shop[--C] = true;
  }
  build_lifting();
  build_centroids();
  while (q--) {
    int I, R;
    cin >> I >> R;
    I--, R--;
    if (!check(R, e, I)) {
      cout << "escaped\n";
    } else {
      long long ans = LLONG_MAX;
      for (int i = 0; i < cnt[R]; i++) {
        if (!check(R, ancestors[R][i], I)) {
          long long x;
          if (!min_excluding[ancestors[R][i]].count(I)) {
            x = dp_val[ancestors[R][i]];
          } else {
            x = min_excluding[ancestors[R][i]][I];
          }
          if (x != LLONG_MAX) {
            ans = min(ans, dis(ancestors[R][i], R) + x); 
          } 
        }
      }
      if (ans == LLONG_MAX) {
        cout << "oo\n";
      } else {
        cout << ans << "\n";
      }
    }
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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