oj.uz

Submission #657332

# Submission time Handle Problem Language Result Execution time Memory
657332 2022-11-09T14:36:06 Z evenvalue Sky Walking (IOI19_walk) C++17
15 / 100
 377 ms 58480 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

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<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int 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 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 0 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 110 ms 22076 KB Output is correct
2 Correct 282 ms 45628 KB Output is correct
3 Correct 312 ms 47428 KB Output is correct
4 Correct 332 ms 56460 KB Output is correct
5 Correct 364 ms 58480 KB Output is correct
6 Correct 377 ms 57632 KB Output is correct
7 Correct 190 ms 34328 KB Output is correct
8 Correct 261 ms 47176 KB Output is correct
9 Correct 334 ms 57764 KB Output is correct
10 Correct 209 ms 51696 KB Output is correct
11 Correct 11 ms 4940 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 22076 KB Output is correct
2 Correct 282 ms 45628 KB Output is correct
3 Correct 312 ms 47428 KB Output is correct
4 Correct 332 ms 56460 KB Output is correct
5 Correct 364 ms 58480 KB Output is correct
6 Correct 377 ms 57632 KB Output is correct
7 Correct 190 ms 34328 KB Output is correct
8 Correct 261 ms 47176 KB Output is correct
9 Correct 334 ms 57764 KB Output is correct
10 Correct 209 ms 51696 KB Output is correct
11 Correct 11 ms 4940 KB Output is correct
12 Correct 301 ms 47436 KB Output is correct
13 Correct 224 ms 56052 KB Output is correct
14 Correct 332 ms 58336 KB Output is correct
15 Correct 262 ms 51632 KB Output is correct
16 Correct 286 ms 56180 KB Output is correct
17 Correct 288 ms 56500 KB Output is correct
18 Correct 258 ms 51604 KB Output is correct
19 Correct 298 ms 56820 KB Output is correct
20 Incorrect 174 ms 33204 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -