Submission #996943

#	Time	Username	Problem	Language	Result	Execution time	Memory
996943		megatron10	Valley (BOI19_valley)	C++17	100 / 100	231 ms	60756 KiB

valley

#include <bits/stdc++.h>
#define ull uint64_t
#define ll long long int
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define mx5 100005
#define mx52 200005
#define mx6 1000005
#define mod 1000000007
#define smod 998244353
#define nfs                     \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x)
{
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)             \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define debug(x...)
#endif

template <typename T>
bool MinPlace(T &a, const T &b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool MaxPlace(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p)
{
  out << "{" << p.ff << ", " << p.ss << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v)
{
  out << "[";
  for (int i = 0; i < (int)v.size(); i++)
  {
    out << v[i];
    if (i != (int)v.size() - 1)
      out << ", ";
  }
  out << "]";
  return out;
}

int main()
{
  nfs;
  const int H = 17;
  const uint64_t inf = 1e14 + 1;
  int n, s, q, root;
  cin >> n >> s >> q >> root;
  vector<array<int, 3>> edges(n);
  vector<vector<pi>> gr(n + 1);
  vi in(n + 1, 0), out(n + 1, 0), depth(n + 1, 0);
  vector<uint64_t> closest(n + 1, inf);
  vector<vi> up(n + 1, vi(H, 0));
  vector<vector<uint64_t>> upEdgeCost(n + 1, vector<uint64_t>(H, 0));
  vector<vector<uint64_t>> upAns(n + 1, vector<uint64_t>(H, inf));
  for (int i = 1; i < n; i++)
  {
    cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    gr[edges[i][0]].pb({edges[i][1], edges[i][2]});
    gr[edges[i][1]].pb({edges[i][0], edges[i][2]});
  }
  for (int i = 0; i < s; i++)
  {
    int u;
    cin >> u;
    closest[u] = 0;
  }
  int timer = 1;
  function<void(int, int, int)> dfs = [&](int u, int p, int d)
  {
    in[u] = ++timer;
    depth[u] = d + 1;
    for (auto [v, w] : gr[u])
    {
      if (v == p)
        continue;
      dfs(v, u, d + 1);
      MinPlace(closest[u], closest[v] + w);
    }
    out[u] = ++timer;
  };
  dfs(root, 0, 0);
  out[0] = ++timer;
  function<bool(int, int)> is_anc = [&](int u, int v)
  {
    return in[u] <= in[v] && out[v] <= out[u];
  };
  function<void(int, int, uint64_t)> dfs2 = [&](int u, int p, uint64_t w)
  {
    up[u][0] = p;
    upEdgeCost[u][0] = w;
    for (int i = 1; i < H; i++)
    {
      up[u][i] = up[up[u][i - 1]][i - 1];
      upEdgeCost[u][i] = upEdgeCost[u][i - 1] + upEdgeCost[up[u][i - 1]][i - 1];
    }
    upAns[u][0] = min(closest[u], w + closest[p]);
    // debug(u, p, w, closest[u], closest[p], upAns[u][0]);
    for (int i = 1; i < H; i++)
      upAns[u][i] = min(upAns[u][i - 1], upEdgeCost[u][i - 1] + upAns[up[u][i - 1]][i - 1]);
    // debug(upAns[u]);
    for (auto [v, wc] : gr[u])
      if (v != p)
        dfs2(v, u, wc);
  };
  dfs2(root, 0, inf);
  // debug(in, out, depth, up);
  // debug(closest);
  // debug(upAns);
  // debug(upEdgeCost);
  while (q--)
  {
    int eno, u;
    cin >> eno >> u;
    auto [a, b, w] = edges[eno];
    if (depth[a] > depth[b])
      swap(a, b);
    if (!is_anc(b, u))
    {
      cout << "escaped\n";
      continue;
    }
    uint64_t ans = closest[u], edgeCost = 0;
    for (int i = H - 1; i >= 0; i--)
    {
      if (depth[up[u][i]] > depth[b])
      {
        MinPlace(ans, edgeCost + upAns[u][i]);
        edgeCost += upEdgeCost[u][i];
        u = up[u][i];
      }
    }
    if (u != b)
    {
      MinPlace(ans, edgeCost + upAns[u][0]);
      edgeCost += upEdgeCost[u][0];
      u = up[u][0];
    }
    if (ans >= inf)
      cout << "oo\n";
    else
      cout << ans << "\n";
  }
}

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