oj.uz

Submission #657349

# Submission time Handle Problem Language Result Execution time Memory
657349 2022-11-09T17:30:24 Z evenvalue Sky Walking (IOI19_walk) C++17
15 / 100
 371 ms 79732 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e17 + 10;
constexpr int kMod = 1e9 + 7;

class LazySegTree {
  const int n;
  vector<int> t;

  void push(const int x, const int l, const int r) {
    if (t[x] == -1) return;
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    for (const int child : {x + 1, y}) {
      t[child] = t[x];
    }
    t[x] = -1;
  }

  void update(const int x, const int l, const int r, const int ql, const int qr, const int i) {
    if (ql <= l and r <= qr) {
      t[x] = i;
      return;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (ql <= mid) {
      update(x + 1, l, mid, ql, qr, i);
    }
    if (mid < qr) {
      update(y, mid + 1, r, ql, qr, i);
    }
  }

  int query(const int x, const int l, const int r, const int p) {
    if (l == r) {
      return t[x];
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (p <= mid) {
      return query(x + 1, l, mid, p);
    } else {
      return query(y, mid + 1, r, p);
    }
  }

public:
  explicit LazySegTree(const int n) : n(n), t(2 * n - 1, -1) {}

  void update(const int l, const int r, const int i) {
    update(0, 0, n - 1, l, r, i);
  }

  int query(const int p) {
    return query(0, 0, n - 1, p);
  }
};


pair<vector<int64>, vector<int>> dijkstra(const vector<vector<pair<int, int>>> &g, const int s) {
  const int n = (int) g.size();

  vector<int64> d(n, kInf64);
  vector<int> p(n, -1);
  min_heap<pair<int64, int>> q;

  d[s] = 0;
  q.push({0, s});

  while (not q.empty()) {
    const auto [dist, x] = q.top();
    q.pop();
    if (d[x] < dist) continue;
    for (const auto &[y, w] : g[x]) {
      if (d[y] <= d[x] + w) continue;
      d[y] = d[x] + w;
      p[y] = x;
      q.push({d[y], y});
    }
  }

  return make_pair(d, p);
}

struct building {
  int x;
  int h;
};

struct skywalk {
  int i;
  int l;
  int r;
  int h;

  bool operator<(const skywalk &other) const {
    return h < other.h;
  }
};

int64 min_distance(vector<int32_t> X, vector<int32_t> H, vector<int32_t> L, vector<int32_t> R, vector<int32_t> Y, int32_t S, int32_t G) {
  const int n = X.size();
  const int m = L.size();

  vector<building> buildings(n);
  for (int i = 0; i < n; i++) {
    buildings[i].h = H[i];
    buildings[i].x = X[i];
  }

  vector<skywalk> skywalks(m);
  for (int j = 0; j < m; j++) {
    skywalks[j].i = j;
    skywalks[j].l = X[L[j]];
    skywalks[j].r = X[R[j]];
    skywalks[j].h = Y[j];
  }

  sort(skywalks.begin(), skywalks.end());

  vector<vector<pair<int, int>>> g(n);
  vector<pair<int, int>> ends(m);
  LazySegTree st(n);

  auto add_node = [&]() -> int {
    g.emplace_back();
    return g.size() - 1;
  };

  auto add_edge = [&](const int x, const int y, const int w) -> void {
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  };

  auto add_vert = [&](const int i, const int h, const int u) {
    const int x = X[i];
    const int s = st.query(i);
    if (s == -1) {
      add_edge(u, i, h);
      return;
    }

    const int v = add_node();
    add_edge(ends[s].first, v, x - X[L[s]]);
    add_edge(ends[s].second, v, X[R[s]] - x);
    add_edge(u, v, h - Y[s]);
  };

  for (const skywalk s : skywalks) {
    const int i = s.i;
    const int l = s.l;
    const int r = s.r;
    const int h = s.h;

    ends[i].first = add_node();
    ends[i].second = add_node();

    add_edge(ends[i].first, ends[i].second, r - l);
    add_vert(L[i], h, ends[i].first);
    add_vert(R[i], h, ends[i].second);

    st.update(L[i], R[i], i);
  }

  const int64 ans = dijkstra(g, S).first[G];
  return (ans == kInf64 ? -1 : ans);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 31008 KB Output is correct
2 Correct 301 ms 65948 KB Output is correct
3 Correct 333 ms 67312 KB Output is correct
4 Correct 358 ms 76464 KB Output is correct
5 Correct 367 ms 78472 KB Output is correct
6 Correct 371 ms 79528 KB Output is correct
7 Correct 185 ms 45608 KB Output is correct
8 Correct 321 ms 60524 KB Output is correct
9 Correct 352 ms 79732 KB Output is correct
10 Correct 229 ms 67948 KB Output is correct
11 Correct 13 ms 6156 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 31008 KB Output is correct
2 Correct 301 ms 65948 KB Output is correct
3 Correct 333 ms 67312 KB Output is correct
4 Correct 358 ms 76464 KB Output is correct
5 Correct 367 ms 78472 KB Output is correct
6 Correct 371 ms 79528 KB Output is correct
7 Correct 185 ms 45608 KB Output is correct
8 Correct 321 ms 60524 KB Output is correct
9 Correct 352 ms 79732 KB Output is correct
10 Correct 229 ms 67948 KB Output is correct
11 Correct 13 ms 6156 KB Output is correct
12 Correct 313 ms 67320 KB Output is correct
13 Correct 248 ms 75964 KB Output is correct
14 Correct 349 ms 78512 KB Output is correct
15 Correct 266 ms 67188 KB Output is correct
16 Correct 320 ms 77092 KB Output is correct
17 Correct 304 ms 77488 KB Output is correct
18 Correct 267 ms 67084 KB Output is correct
19 Correct 326 ms 75544 KB Output is correct
20 Incorrect 180 ms 44428 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -