Submission #1146956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146956		akamizane	Valley (BOI19_valley)	C++20	23 / 100	152 ms	43540 KiB

valley

#include<bits/stdc++.h>

using namespace std;
 

#define debug(...) 40

 
using ll = long long;
using pii = pair<int, int>;
using db = long double;

#define int long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}

const int maxn = 1e5 + 5;
const int mod = 998244353;
const ll inf = 1e18;

vector<pii> ad[maxn];
vector<pii> edge;
int in[maxn], out[maxn], shop[maxn], d[maxn], x[maxn], dp[maxn], par[maxn][18], mn[maxn][18];
int timedDfs = 0;

void dfs(int u, int p){
  in[u] = timedDfs++;
  par[u][0] = p;
  if (shop[u]){
    x[u] = d[u];
  }
  for (auto [v, w] : ad[u]){
    if (v == p) continue;
    d[v] = d[u] + w;
    dfs(v, u);
    x[u] = min(x[u], x[v]);
  }
  dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
  mn[u][0] = dp[u];
  out[u] = timedDfs++;
}

bool is_anc(int u, int v){
  return in[u] <= in[v] && out[v] <= out[u];
}

void solve(){
  int n, s, q, e;
  cin >> n >> s >> q >> e;
  for (int i = 0; i < n - 1; i++){
    int u, v, w;
    cin >> u >> v >> w;
    edge.pb({u, v});
    ad[u].pb({v, w});
    ad[v].pb({u, w});
  }
  for (int i = 0; i < s; i++){
    int x;
    cin >> x;
    shop[x] = 1;
  }
  FOR(i, 1, n) x[i] = inf, d[i] = 0;
  dfs(e, e);
  for (int cnt = 1; cnt < 18; cnt++){
    for (int i = 0; i < n; i++){
      par[i][cnt] = par[par[i][cnt - 1]][cnt - 1];
      mn[i][cnt] = min(mn[i][cnt - 1], mn[par[i][cnt - 1]][cnt - 1]);
    }
  }
  while(q--){
    int i, r;
    cin >> i >> r;
    i--;
    auto [u, v] = edge[i];
    debug(u, v);
    if (is_anc(u, v)) swap(u, v);
    if (!is_anc(u, r)){
      cout << "escaped\n";
    }
    else{
      // fix the lca u, find the index v in subtree of u such that 2 * d[u] - d[v] is min
      int best = dp[u], dist = d[r];
      for (int cnt = 17; cnt >= 0; cnt--){
        if (is_anc(u, par[r][cnt])){
          best = min(best, mn[r][cnt]);
          r = par[r][cnt];
        }
      }
      if (best == inf) cout << "oo\n";
      else cout << dist + best << "\n";
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    // cerr << "- Case #" << _ << ": \n";
    solve();
    // cout << "\n";
  }
  return 0;
}

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