oj.uz

Submission #657350

# Submission time Handle Problem Language Result Execution time Memory
657350 2022-11-09T17:31:02 Z evenvalue Sky Walking (IOI19_walk) C++17
15 / 100
 391 ms 77708 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 = 1e18 + 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 0 ms 212 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 121 ms 30424 KB Output is correct
2 Correct 310 ms 64372 KB Output is correct
3 Correct 358 ms 65268 KB Output is correct
4 Correct 369 ms 74508 KB Output is correct
5 Correct 391 ms 76500 KB Output is correct
6 Correct 379 ms 77388 KB Output is correct
7 Correct 196 ms 43600 KB Output is correct
8 Correct 309 ms 58436 KB Output is correct
9 Correct 388 ms 77708 KB Output is correct
10 Correct 275 ms 66012 KB Output is correct
11 Correct 13 ms 5312 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 30424 KB Output is correct
2 Correct 310 ms 64372 KB Output is correct
3 Correct 358 ms 65268 KB Output is correct
4 Correct 369 ms 74508 KB Output is correct
5 Correct 391 ms 76500 KB Output is correct
6 Correct 379 ms 77388 KB Output is correct
7 Correct 196 ms 43600 KB Output is correct
8 Correct 309 ms 58436 KB Output is correct
9 Correct 388 ms 77708 KB Output is correct
10 Correct 275 ms 66012 KB Output is correct
11 Correct 13 ms 5312 KB Output is correct
12 Correct 333 ms 65232 KB Output is correct
13 Correct 265 ms 73928 KB Output is correct
14 Correct 363 ms 76448 KB Output is correct
15 Correct 287 ms 65196 KB Output is correct
16 Correct 332 ms 75208 KB Output is correct
17 Correct 329 ms 75400 KB Output is correct
18 Correct 272 ms 65000 KB Output is correct
19 Correct 330 ms 73588 KB Output is correct
20 Incorrect 197 ms 42508 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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