oj.uz

Submission #657824

# Submission time Handle Problem Language Result Execution time Memory
657824 2022-11-11T12:15:43 Z evenvalue Sky Walking (IOI19_walk) C++17
33 / 100
 414 ms 80284 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 l;
  int r;
  int h;

  set<pair<int, int>> nodes;

  bool operator<(const skywalk &other) const {
    if (h != other.h) return h < other.h;
    if (l != other.l) return l < other.l;
    return r < other.r;
  }

  void add_node(const int node, const int x) {
    nodes.insert({x, node});
  }

  pair<int, int> get_prev(const int x) const {
    return *prev(nodes.upper_bound({x, kInf}));
  }

  pair<int, int> get_next(const int x) const {
    return *nodes.upper_bound({x, -1});
  }
};

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].l = L[j];
    skywalks[j].r = R[j];
    skywalks[j].h = Y[j];
  }

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

  vector<vector<pair<int, int>>> g(n);
  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();

    auto before = skywalks[s].get_prev(x);
    add_edge(before.second, v, x - before.first);

    auto after = skywalks[s].get_next(x);
    add_edge(after.second, v, after.first - x);
    add_edge(u, v, h - skywalks[s].h);

    skywalks[s].add_node(v, x);
  };

  for (int i = 0; i < skywalks.size(); i++) {
    skywalk &s = skywalks[i];

    const int l = s.l;
    const int r = s.r;
    const int h = s.h;

    const int x = add_node();
    const int y = add_node();

    add_edge(x, y, X[r] - X[l]);
    add_vert(l, h, x);
    add_vert(r, h, y);

    s.add_node(x, X[l]);
    s.add_node(y, X[r]);

    st.update(l, r, 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:182:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<skywalk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |   for (int i = 0; i < skywalks.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp:202: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]
  202 |   for (int x = 0; x < g.size(); x++) {
      |                   ~~^~~~~~~~~~
walk.cpp:203:21: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  203 |     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 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 113 ms 32372 KB Output is correct
2 Correct 364 ms 67600 KB Output is correct
3 Correct 371 ms 68324 KB Output is correct
4 Correct 411 ms 75684 KB Output is correct
5 Correct 395 ms 76984 KB Output is correct
6 Correct 414 ms 76600 KB Output is correct
7 Correct 207 ms 42768 KB Output is correct
8 Correct 365 ms 61880 KB Output is correct
9 Correct 390 ms 77100 KB Output is correct
10 Correct 220 ms 69108 KB Output is correct
11 Correct 11 ms 5004 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 32372 KB Output is correct
2 Correct 364 ms 67600 KB Output is correct
3 Correct 371 ms 68324 KB Output is correct
4 Correct 411 ms 75684 KB Output is correct
5 Correct 395 ms 76984 KB Output is correct
6 Correct 414 ms 76600 KB Output is correct
7 Correct 207 ms 42768 KB Output is correct
8 Correct 365 ms 61880 KB Output is correct
9 Correct 390 ms 77100 KB Output is correct
10 Correct 220 ms 69108 KB Output is correct
11 Correct 11 ms 5004 KB Output is correct
12 Correct 364 ms 68292 KB Output is correct
13 Correct 287 ms 75348 KB Output is correct
14 Correct 382 ms 76948 KB Output is correct
15 Correct 290 ms 66724 KB Output is correct
16 Correct 317 ms 74948 KB Output is correct
17 Correct 345 ms 74612 KB Output is correct
18 Correct 279 ms 66764 KB Output is correct
19 Correct 322 ms 75188 KB Output is correct
20 Correct 208 ms 42552 KB Output is correct
21 Correct 29 ms 10764 KB Output is correct
22 Correct 249 ms 66780 KB Output is correct
23 Correct 252 ms 69008 KB Output is correct
24 Correct 273 ms 65220 KB Output is correct
25 Correct 262 ms 64920 KB Output is correct
26 Correct 233 ms 58916 KB Output is correct
27 Correct 414 ms 79244 KB Output is correct
28 Correct 299 ms 77968 KB Output is correct
29 Correct 396 ms 79228 KB Output is correct
30 Correct 214 ms 44548 KB Output is correct
31 Correct 372 ms 80284 KB Output is correct
32 Correct 217 ms 67880 KB Output is correct
33 Correct 207 ms 67456 KB Output is correct
34 Correct 234 ms 70812 KB Output is correct
35 Correct 243 ms 68644 KB Output is correct
36 Correct 276 ms 66016 KB Output is correct
37 Correct 217 ms 64476 KB Output is correct
38 Correct 200 ms 63660 KB Output is correct
39 Correct 253 ms 71452 KB Output is correct
40 Correct 221 ms 64920 KB Output is correct
41 Correct 238 ms 64044 KB Output is correct

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 -