Submission #1365320

#TimeUsernameProblemLanguageResultExecution timeMemory
1365320behradValley (BOI19_valley)C++20
100 / 100
120 ms25920 KiB
#ifdef LOCAL
#include "/home/bgopc/template/pch.hpp"
#endif
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, S, s[maxn], in[maxn], out[maxn], T = 1, Ev, seq[maxn], q;
ll seg[maxn << 2], lazy[maxn << 2], ans[maxn], h[maxn];
pii E[maxn];
vector<pii> g[maxn];
vector<pii> Q[maxn];

void build(int l, int r, int id) {
  lazy[id] = 0;
  if (r - l == 1) {
    int v = seq[l];
    if (s[v]) seg[id] = h[v];
    else seg[id] = inf;
    return;
  }

  int mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  build(l, mid, lc);
  build(mid, r, rc);
  seg[id] = min(seg[lc], seg[rc]);
}

inline void tag(int id, ll x) {
  seg[id] += x;
  lazy[id] += x;
}

inline void relax(int id) {
  if (!lazy[id]) return ;
  tag(id << 1, lazy[id]);
  tag(id << 1 | 1, lazy[id]);
  lazy[id] = 0;
}

void update(int ql, int qr, ll x, int l = 1, int r = n+1, int id = 1) {
  if (ql <= l && r <= qr) return tag(id, x);
  if (qr <= l || r <= ql) return ;
  relax(id);

  int mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  update(ql, qr, x, l, mid, lc);
  update(ql, qr, x, mid, r, rc);
  seg[id] = min(seg[lc], seg[rc]);
}

ll get(int ql, int qr, int l = 1, int r = n+1, int id = 1) {
  if (ql <= l && r <= qr) return seg[id];
  if (qr <= l || r <= ql) return inf;
  relax(id);
  int mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  return min(get(ql, qr, l, mid, lc), get(ql, qr, mid, r, rc));
}

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

void PreDfs(int v, int p = 0) {
  in[v] = T ++;
  seq[in[v]] = v;
  for (auto [u, w] : g[v]) {
    if (u != p) {
      h[u] = h[v] + w;
      PreDfs(u, v);
    }
  }
  out[v] = T;
}

void dfs(int v, int p = 0, ll w = 0) {
  update(1, n + 1, w);
  update(in[v], out[v], -2 * w);

  for (auto [u, j] : Q[v]) {
    if (isfa(u, v)) {
      ans[j] = min(ans[j], get(in[u], out[u]));
    } else {
      ans[j] = min(ans[j], get(1, in[u]));
      ans[j] = min(ans[j], get(out[u], n + 1));
    }
  }

  for (auto [u, w] : g[v]) {
    if (u != p) dfs(u, v, w);
  }

  update(1, n + 1, -w);
  update(in[v], out[v], 2 * w);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> S >> q >> Ev;
  for (int i = 1 , u , v , w ; i < n ; i ++) {
    cin >> u >> v >> w;
    g[u].pb({v, w});
    g[v].pb({u, w});
    E[i] = {u, v};
  }
  for (int i = 1 , c ; i <= S ; i ++) cin >> c, s[c] = 1;

  PreDfs(1);
  for (int i = 1 ; i < n ; i ++) if (in[E[i].ss] < in[E[i].ff]) swap(E[i].ff, E[i].ss);

  build(1, n + 1, 1);

  for (int i = 1 , I , u ; i <= q ; i ++) {
    cin >> I >> u;
    int v = E[I].ss;
    if (isfa(v, u) ^ isfa(v, Ev)) {
      ans[i] = inf;
      Q[u].pb({v, i});
    } else ans[i] = -1;
  }

  dfs(1);

  for (int i = 1 ; i <= q ; i ++) {
    if (ans[i] == -1) cout << "escaped\n";
    else if (ans[i] >= 2e14) cout << "oo\n";
    else cout << ans[i] << nl;
  }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...