Submission #1352566

#TimeUsernameProblemLanguageResultExecution timeMemory
1352566thewizardmanValley (BOI19_valley)C++20
100 / 100
122 ms48188 KiB
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ms(x, y) memset(x, y, sizeof x)
#define sp ,' ',
#define el ,'\n'
using namespace std;
using ll = long long;
using ld = long double;
using pil = pair<int, ll>;

template<typename... Args>
inline void out(Args... args) {
  (cout << ... << args);
}

struct r {
  template<typename T>
  inline r& operator,(T& x) {
    cin >> x;
    return *this;
  }
} in;
#define in in,

int n, s, q, e;
vector<pil> adj[100005];
bool shop[100005];

int de[100005], pa[17][100005], edge[100005][2];
ll dist[17][100005], sum[17][100005];

void dfs(int u, int p) {
  de[u] = de[p] + 1;
  pa[0][u] = p;
  if (shop[u]) dist[0][u] = 0;
  for (auto &[v, w]: adj[u]) if (v != p) dfs(v, u);
  for (auto &[v, w]: adj[u]) if (v != p) {
    dist[0][u] = min(dist[0][u], dist[0][v] + w);
    sum[0][v] = w;
  }
}

int anc(int u, int v) {
  if (de[u] > de[v]) return -1;
  int d = de[v] - de[u];
  for (int i = 0; i <= 16; i++) if ((d>>i) & 1) v = pa[i][v];
  if (u == v) return d;
  else return -1;
}

void solve() {
  in n,s,q,e;
  for (int i = 1; i < n; i++) {
    int u,v; ll w; in u,v,w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    edge[i][0] = u;
    edge[i][1] = v;
  }
  while (s--) {
    int c; in c;
    shop[c] = 1;
  }
  ms(dist, 0x3f);
  dfs(e, e);
  for (int j = 1; j <= 16; j++) for (int i = 1; i <= n; i++) {
    int anc = pa[j-1][i];
    pa[j][i] = pa[j-1][anc];
    dist[j][i] = min(dist[j-1][i], dist[j-1][anc] + sum[j-1][i]);
    sum[j][i] = sum[j-1][i] + sum[j-1][anc];
  }
  while (q--) {
    int i, u; in i, u;
    int d = min(anc(edge[i][0], u), anc(edge[i][1], u));
    if (d == -1) out("escaped\n");
    else {
      ll di = LLONG_MAX, su = 0;
      d++;
      for (int j = 0; j <= 16; j++) if ((d>>j) & 1) {
        int a = pa[j][u];
        di = min(di, su + dist[j][u]);
        su += sum[j][u];
        u = pa[j][u];
      }
      if (di < 4e18) out(di el);
      else out("oo\n");
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t = 1;
  // in(t);
  while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...