oj.uz

Submission #657694

# Submission time Handle Problem Language Result Execution time Memory
657694 2022-11-10T17:26:58 Z evenvalue Sky Walking (IOI19_walk) C++17
15 / 100
 411 ms 58488 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 ? h < other.h : l < other.l);
  }
};

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);
  }

  for (int x = 0; x < g.size(); x++) {
    for (const auto [y, w] : g[x]) {
//      cout << x << ' ' << y << ' ' << w << '\n';
    }
  }

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

Compilation message

walk.cpp: In function 'int64 min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:179:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   for (int x = 0; x < g.size(); x++) {
      |                   ~~^~~~~~~~~~
walk.cpp:180:21: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  180 |     for (const auto [y, w] : g[x]) {
      |                     ^~~~~~

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 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 81 ms 22088 KB Output is correct
2 Correct 307 ms 46388 KB Output is correct
3 Correct 341 ms 47396 KB Output is correct
4 Correct 365 ms 56420 KB Output is correct
5 Correct 367 ms 58488 KB Output is correct
6 Correct 411 ms 57584 KB Output is correct
7 Correct 216 ms 34384 KB Output is correct
8 Correct 283 ms 47016 KB Output is correct
9 Correct 337 ms 57732 KB Output is correct
10 Correct 177 ms 51736 KB Output is correct
11 Correct 13 ms 4948 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 22088 KB Output is correct
2 Correct 307 ms 46388 KB Output is correct
3 Correct 341 ms 47396 KB Output is correct
4 Correct 365 ms 56420 KB Output is correct
5 Correct 367 ms 58488 KB Output is correct
6 Correct 411 ms 57584 KB Output is correct
7 Correct 216 ms 34384 KB Output is correct
8 Correct 283 ms 47016 KB Output is correct
9 Correct 337 ms 57732 KB Output is correct
10 Correct 177 ms 51736 KB Output is correct
11 Correct 13 ms 4948 KB Output is correct
12 Correct 366 ms 47472 KB Output is correct
13 Correct 227 ms 55952 KB Output is correct
14 Correct 398 ms 58356 KB Output is correct
15 Correct 285 ms 51636 KB Output is correct
16 Correct 250 ms 56172 KB Output is correct
17 Correct 282 ms 56572 KB Output is correct
18 Correct 310 ms 51576 KB Output is correct
19 Correct 310 ms 56732 KB Output is correct
20 Incorrect 169 ms 33188 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 -