oj.uz

Submission #657825

# Submission time Handle Problem Language Result Execution time Memory
657825 2022-11-11T12:29:17 Z evenvalue Sky Walking (IOI19_walk) C++17
33 / 100
 403 ms 76572 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);
  }

  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:183:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<skywalk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |   for (int i = 0; i < skywalks.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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 102 ms 31788 KB Output is correct
2 Correct 359 ms 67004 KB Output is correct
3 Correct 368 ms 67632 KB Output is correct
4 Correct 403 ms 74764 KB Output is correct
5 Correct 396 ms 76024 KB Output is correct
6 Correct 387 ms 75540 KB Output is correct
7 Correct 208 ms 41868 KB Output is correct
8 Correct 356 ms 60796 KB Output is correct
9 Correct 385 ms 76060 KB Output is correct
10 Correct 216 ms 68028 KB Output is correct
11 Correct 11 ms 4308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 31788 KB Output is correct
2 Correct 359 ms 67004 KB Output is correct
3 Correct 368 ms 67632 KB Output is correct
4 Correct 403 ms 74764 KB Output is correct
5 Correct 396 ms 76024 KB Output is correct
6 Correct 387 ms 75540 KB Output is correct
7 Correct 208 ms 41868 KB Output is correct
8 Correct 356 ms 60796 KB Output is correct
9 Correct 385 ms 76060 KB Output is correct
10 Correct 216 ms 68028 KB Output is correct
11 Correct 11 ms 4308 KB Output is correct
12 Correct 362 ms 67652 KB Output is correct
13 Correct 284 ms 74320 KB Output is correct
14 Correct 381 ms 75780 KB Output is correct
15 Correct 283 ms 65716 KB Output is correct
16 Correct 309 ms 73908 KB Output is correct
17 Correct 333 ms 73524 KB Output is correct
18 Correct 268 ms 65668 KB Output is correct
19 Correct 316 ms 74268 KB Output is correct
20 Correct 207 ms 41544 KB Output is correct
21 Correct 26 ms 8996 KB Output is correct
22 Correct 248 ms 63392 KB Output is correct
23 Correct 259 ms 65504 KB Output is correct
24 Correct 265 ms 61616 KB Output is correct
25 Correct 275 ms 61572 KB Output is correct
26 Correct 227 ms 55396 KB Output is correct
27 Correct 382 ms 75500 KB Output is correct
28 Correct 287 ms 74148 KB Output is correct
29 Correct 385 ms 75504 KB Output is correct
30 Correct 224 ms 41788 KB Output is correct
31 Correct 383 ms 76572 KB Output is correct
32 Correct 214 ms 64928 KB Output is correct
33 Correct 204 ms 64412 KB Output is correct
34 Correct 238 ms 67932 KB Output is correct
35 Correct 237 ms 65896 KB Output is correct
36 Correct 257 ms 63208 KB Output is correct
37 Correct 212 ms 62012 KB Output is correct
38 Correct 195 ms 60808 KB Output is correct
39 Correct 246 ms 68816 KB Output is correct
40 Correct 212 ms 62012 KB Output is correct
41 Correct 233 ms 61628 KB Output is correct

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 -