Submission #1127564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127564		omtheprogrammer1	Valley (BOI19_valley)	C++20	0 / 100	162 ms	65588 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp make_pair
#define pb push_back
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define ins insert
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define sz(v) (ll)v.size()
#define readgraph(list, edges) for (ll i = 0; i < edges; i++) {ll a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define F_OR(i, a, b, s) for (ll i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

ll prexor(ll i) {
  i++;
  if ((i % 4) == 0) return 0;
  else if ((i % 4) == 1) return i - 1;
  else if ((i % 4) == 2) return 1;
  else return i;
}
ll rangexor(ll l, ll r) {
  if (l == 0) return prexor(r);
  return prexor(r)^prexor(l - 1);
}
ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb) / 2;
    f(mb) ? rb = mb : lb = mb + 1;
  }
  return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb + 1) / 2;
    f(mb) ? lb = mb : rb = mb - 1;
  }
  return lb;
}

template<class A> void read(vector<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template<class A> void read(vector<A>& x) {
  EACH(a, x)
  read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
  EACH(a, x)
  read(a);
}

// #define cerr cout
namespace __DEBUG_UTIL__
{
/* Primitive Datatypes Print */
void print(const char *x) { cerr << x; }
void print(bool x) { cerr << (x ? "T" : "F"); }
void print(char x) { cerr << '\'' << x << '\''; }
void print(signed short int x) { cerr << x; }
void print(unsigned short int x) { cerr << x; }
void print(signed int x) { cerr << x; }
void print(unsigned int x) { cerr << x; }
void print(signed long int x) { cerr << x; }
void print(unsigned long int x) { cerr << x; }
void print(signed long long int x) { cerr << x; }
void print(unsigned long long int x) { cerr << x; }
void print(float x) { cerr << x; }
void print(double x) { cerr << x; }
void print(long double x) { cerr << x; }
void print(string x) { cerr << '\"' << x << '\"'; }
template <size_t N>
void print(bitset<N> x) { cerr << x; }
void print(vector<bool> v)
{ /* Overloaded this because stl optimizes vector<bool> by using
      _Bit_reference instead of bool to conserve space. */
  int f = 0;
  cerr << '{';
  for (auto && i : v)
    cerr << (f++ ? "," : "") << (i ? "T" : "F");
  cerr << "}";
}
/* Templates Declarations to support nested datatypes */
template <typename T>
void print(T &&x);
template <typename T>
void print(vector<vector<T>> mat);
template <typename T, size_t N, size_t M>
void print(T (&mat)[N][M]);
template <typename F, typename S>
void print(pair<F, S> x);
template <typename T, size_t N>
struct Tuple;
template <typename T>
struct Tuple<T, 1>;
template <typename... Args>
void print(tuple<Args...> t);
template <typename... T>
void print(priority_queue<T...> pq);
template <typename T>
void print(stack<T> st);
template <typename T>
void print(queue<T> q);
/* Template Datatypes Definitions */
template <typename T>
void print(T &&x)
{
  /*  This works for every container that supports range-based loop
      i.e. vector, set, map, oset, omap, dequeue */
  int f = 0;
  cerr << '{';
  for (auto && i : x)
    cerr << (f++ ? "," : ""), print(i);
  cerr << "}";
}
template <typename T>
void print(vector<vector<T>> mat)
{
  int f = 0;
  cerr << "\n~~~~~\n";
  for (auto && i : mat)
  {
    cerr << setw(2) << left << f++, print(i), cerr << "\n";
  }
  cerr << "~~~~~\n";
}
template <typename T, size_t N, size_t M>
void print(T (&mat)[N][M])
{
  int f = 0;
  cerr << "\n~~~~~\n";
  for (auto && i : mat)
  {
    cerr << setw(2) << left << f++, print(i), cerr << "\n";
  }
  cerr << "~~~~~\n";
}
template <typename F, typename S>
void print(pair<F, S> x)
{
  cerr << '(';
  print(x.first);
  cerr << ',';
  print(x.second);
  cerr << ')';
}
template <typename T, size_t N>
struct Tuple
{
  static void printTuple(T t)
  {
    Tuple < T, N - 1 >::printTuple(t);
    cerr << ",", print(get < N - 1 > (t));
  }
};
template <typename T>
struct Tuple<T, 1>
{
  static void printTuple(T t) { print(get<0>(t)); }
};
template <typename... Args>
void print(tuple<Args...> t)
{
  cerr << "(";
  Tuple<decltype(t), sizeof...(Args)>::printTuple(t);
  cerr << ")";
}
template <typename... T>
void print(priority_queue<T...> pq)
{
  int f = 0;
  cerr << '{';
  while (!pq.empty())
    cerr << (f++ ? "," : ""), print(pq.top()), pq.pop();
  cerr << "}";
}
template <typename T>
void print(stack<T> st)
{
  int f = 0;
  cerr << '{';
  while (!st.empty())
    cerr << (f++ ? "," : ""), print(st.top()), st.pop();
  cerr << "}";
}
template <typename T>
void print(queue<T> q)
{
  int f = 0;
  cerr << '{';
  while (!q.empty())
    cerr << (f++ ? "," : ""), print(q.front()), q.pop();
  cerr << "}";
}
/* Printer functions */
void printer(const char *) {} /* Base Recursive */
template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail)
{
  /* Using && to capture both lvalues and rvalues */
  int i = 0;
  for (size_t bracket = 0; names[i] != '\0' and (names[i] != ',' or bracket != 0); i++)
    if (names[i] == '(' or names[i] == '<' or names[i] == '{')
      bracket++;
    else if (names[i] == ')' or names[i] == '>' or names[i] == '}')
      bracket--;
  cerr.write(names, i) << " = ";
  print(head);
  if (sizeof...(tail))
    cerr << " ||", printer(names + i + 1, tail...);
  else
    cerr << "]\n";
}
/* PrinterArr */
void printerArr(const char *) {} /* Base Recursive */
template <typename T, typename... V>
void printerArr(const char *names, T arr[], size_t N, V... tail)
{
  size_t ind = 0;
  for (; names[ind] and names[ind] != ','; ind++)
    cerr << names[ind];
  for (ind++; names[ind] and names[ind] != ','; ind++)
    ;
  cerr << " = {";
  for (size_t i = 0; i < N; i++)
    cerr << (i ? "," : ""), print(arr[i]);
  cerr << "}";
  if (sizeof...(tail))
    cerr << " ||", printerArr(names + ind + 1, tail...);
  else
    cerr << "]\n";
}
}

#define debug(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__);
#define debugArr(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__);


mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
  return uniform_int_distribution<ll>(a, b)(mt_rng);
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const ll INF = 1e17;
const int d4i[4] = { -1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = { -1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int kni[8] = { +2, +2, -2, -2, 1, -1, 1, -1}, knj[8] = {1, -1, 1, -1, 2, 2, -2, -2};

ll n, m, k, q, l, r, x, y, z , h, s, e, w;
const ll tas = 2e5 + 10;
ll a[tas];
ll dp1[tas];
ll dp2[tas];
ll par[tas];
ll in[tas];
ll out[tas];
ll dep[tas];
ll d1[tas];
ll lift[tas][20];
ll lval[tas][20];
ll tval[tas][20];
string t;
vector<pii> grid[tas];
// vector<pii> edges[tas];
ll ans = 0, timer = 0;

void dfs1(int cur, int pr = -1) {
  dp1[cur] = (a[cur] ? 0ll : INF);
  par[cur] = pr;
  in[cur] = timer++;
  for (auto val : grid[cur]) {
    if (val.f != pr) {
      d1[val.f] = d1[cur] + 1;
      dep[val.f] = dep[cur] + val.s;
      dfs1(val.f, cur);
      dp1[cur] = min(dp1[val.f] + val.s, dp1[cur]);
    }
  }
  out[cur] = timer++;
}

void dfs2(int cur, ll pcon = INF) {
  dp2[cur] = pcon;
  vector<pii> ch;
  for (auto val : grid[cur]) {
    if (par[cur] != val.f) {
      ch.pb(val);
    }
  }
  vector<ll> pre;
  vector<ll> suf;
  for (auto val : ch) pre.pb(dp1[val.f] + val.s);
  for (auto val : ch) suf.pb(dp1[val.f] + val.s);
  FOR(sz(pre) - 1)pre[i + 1] = min(pre[i + 1], pre[i]);
  FOR(i, sz(pre) - 1, 0, -1)suf[i - 1] = min(suf[i - 1], suf[i]);
  int ti = 0;
  for (auto val : ch) {
    l = (ti ? pre[ti - 1] : INF);
    // debug(cur, val.f, pre, pre[ti - 1])
    r = ((ti != (sz(pre) - 1)) ? suf[ti + 1] : INF);
    dfs2(val.f, min(l, r));
    ti++;
  }
  // debug(cur, dp1[cur])
  // debug(dp1[cur], pre)
  // debug(suf)
}

ll get(ll x, ll y) {
  ll temp = INF;
  FOR(20) if ((1ll << i)&y) {
    temp = min(temp, lval[x][i]), x = lift[x][i];
  }
  return temp;
}

ll tget(ll x, ll y) {
  ll temp = INF;
  FOR(20) if ((1ll << i)&y) {
    temp = min(temp, tval[x][i]), x = lift[x][i];
  }
  return temp;
}

ll lca(ll x, ll y) {
  if (d1[x] < d1[y]) swap(x, y);
  int k = d1[x] - d1[y];
  FOR(20) if ((1ll << i)&k) x = lift[x][i];
  if (x == y) return x;
  FOR(i, 19, -1, -1) if (lift[x][i] != lift[y][i])
    x = lift[x][i], y = lift[y][i];
  return lift[x][0];
}

void solve(int tc = 0) {

  cin >> n >> s >> q >> e;
  e--;
  vector<pii> vec;
  FOR(n - 1) {
    cin >> x >> y >> z;
    x--, y--;
    vec.pb(mp(x, y));
    grid[x].pb(mp(y, z));
    grid[y].pb(mp(x, z));
  }

  FOR(s) {
    cin >> x;
    x--;
    a[x] = 1;
  }
  dfs1(0);
  dfs2(0);
  FOR(n) {
    lift[i][0] = par[i], lval[i][0] = dp2[i] - dep[par[i]], tval[i][0] = dp2[i] + dep[par[i]];
  }
  FOR(i, 1, 20) {
    FOR(j, 0, n) {
      lift[j][i] = lift[lift[j][i - 1]][i - 1];
      lval[j][i] = min(lval[j][i - 1], lval[lift[j][i - 1]][i - 1]);
      tval[j][i] = min(tval[j][i - 1], tval[lift[j][i - 1]][i - 1]);
    }
  }
  FOR(q) {
    cin >> x >> y;
    x--;
    y--;
    ll tx = vec[x].f, ty = vec[x].s;
    if (dep[tx] > dep[ty]) swap(tx, ty);
    ll tans = 0;
    if (in[ty] <= in[y] && out[y] <= out[ty]) tans++;
    if (in[ty] <= in[e] && out[e] <= out[ty]) tans++;
    if (tans != 1) {
      cout << "escaped" << endl;
      continue;
    }
    if (in[ty] <= in[y] && out[y] <= out[ty]) {
      ll dist = d1[y] - d1[ty];
      tans = INF;
      tans = dp1[y];
      tans = min(tans, dep[y] + get(y, dist));
      if (tans >= 1e15) {
        cout << "oo" << endl;
      }
      else cout << tans << endl;
      continue;
    }
    else {
      tans = dp1[y];
      ll lc = lca(y, tx);
      if (lc != y)
        tans = min(tans, dep[y] + get(y, d1[y] - d1[lc] - 1));
      tans = min(tans, dep[y] + get(lc, d1[lc]));
      tans = min(tans, -dep[y] + tget(ty, d1[tx] - d1[lc] + 1));
      // debug(tans)
      if (tans >= 1e15) {
        cout << "oo" << endl;
      }
      else cout << tans << endl;
    }

  }
}

int main() {
  fastio

#ifdef LOCAL
  auto begin = std::chrono::high_resolution_clock::now();
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);
#endif

  ll tc = 1;
  // cin >> tc;
  for (int t = 0; t < tc; t++) solve(t);
#ifdef LOCAL
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
  // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
}

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