oj.uz

Submission #996943

# Submission time Handle Problem Language Result Execution time Memory
996943 2024-06-11T13:43:25 Z megatron10 Valley (BOI19_valley) C++17
100 / 100
 231 ms 60756 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 1 ms 824 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 53328 KB Output is correct
2 Correct 155 ms 53072 KB Output is correct
3 Correct 162 ms 53024 KB Output is correct
4 Correct 200 ms 55892 KB Output is correct
5 Correct 186 ms 55944 KB Output is correct
6 Correct 231 ms 59220 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 1 ms 824 KB Output is correct
15 Correct 163 ms 53328 KB Output is correct
16 Correct 155 ms 53072 KB Output is correct
17 Correct 162 ms 53024 KB Output is correct
18 Correct 200 ms 55892 KB Output is correct
19 Correct 186 ms 55944 KB Output is correct
20 Correct 231 ms 59220 KB Output is correct
21 Correct 144 ms 53588 KB Output is correct
22 Correct 143 ms 53196 KB Output is correct
23 Correct 147 ms 53076 KB Output is correct
24 Correct 177 ms 56400 KB Output is correct
25 Correct 219 ms 60756 KB Output is correct
26 Correct 152 ms 53572 KB Output is correct
27 Correct 145 ms 53172 KB Output is correct
28 Correct 164 ms 53076 KB Output is correct
29 Correct 186 ms 55252 KB Output is correct
30 Correct 206 ms 57424 KB Output is correct
31 Correct 157 ms 53456 KB Output is correct
32 Correct 140 ms 53120 KB Output is correct
33 Correct 160 ms 53248 KB Output is correct
34 Correct 212 ms 56024 KB Output is correct
35 Correct 214 ms 60496 KB Output is correct
36 Correct 179 ms 56916 KB Output is correct