Submission #1306704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306704		chrisvilches	Walk (CEOI06_walk)	C++20	100 / 100	199 ms	31544 KiB

walk

#include <bits/stdc++.h>
using namespace std;
// TODO: There are a few TODOs to understand some aspects of the logic better.
// TODO: Add to sweep line category.
// TODO: Is this DP? add to DP category???

struct Point {
  int x, y;
  Point operator-(const Point p) const { return {x - p.x, y - p.y}; }
  bool operator==(const Point p) const { return x == p.x && y == p.y; }
  int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
  struct Hash {
    size_t operator()(const Point p) const noexcept {
      return (static_cast<size_t>(p.x) << 32) ^ static_cast<size_t>(p.y);
    }
  };
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  Point dest;
  while (cin >> dest.x >> dest.y >> n) {
    vector<tuple<int, int, int, int>> events;

    for (int i = 0; i < n; i++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      assert(x1 <= x2 && y1 <= y2);
      if (dest.x < x1) continue;

      events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
      events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);
    }

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

    map<int, int> active;
    unordered_map<Point, Point, Point::Hash> parent;
    unordered_map<Point, int, Point::Hash> dist;

    active[0] = 0;
    active[INT_MIN] = 0;
    active[INT_MAX] = 0;

    dist[{0, 0}] = 0;

    const auto update = [&](const Point p) {
      const auto it0 = active.lower_bound(p.y);
      const auto it1 = prev(it0);

      for (const auto it : {it0, it1}) {
        const Point prev{it->second, it->first};

        if (!dist.count(prev)) continue;
        const int new_dist = dist[prev] + p.dist(prev);

        if (!dist.count(p) || dist[p] > new_dist) {
          dist[p] = new_dist;
          parent[p] = prev;
        }

        // TODO: This line is suspicious. Without it, it gets WA
        // Maybe it's because of the ordering of events and some premises
        // about the ordering and how points are processed??
        if (it0->first == p.y) break;
      }

      active[p.y] = p.x;
    };

    for (const auto& [x, _, y1, y2] : events) {
      update({x, y1});
      update({x, y2});

      while (true) {
        const auto it = active.lower_bound(y1 + 1);
        if (y2 <= it->first) break;
        active.erase(it);
      }
    }

    update(dest);

    vector<Point> path;
    Point curr = dest;

    while (curr.x != 0 || curr.y != 0) {
      path.emplace_back(curr);
      curr = parent[curr];
    }

    path.emplace_back(curr);

    reverse(path.begin(), path.end());

    vector<Point> deltas;

    const auto add_delta = [&](const Point d) {
      if (!deltas.empty() &&
          ((deltas.back().x == 0 && d.x == 0) || (deltas.back().y == 0 && d.y == 0))) {
        deltas.back().x += d.x;
        deltas.back().y += d.y;
      } else {
        deltas.emplace_back(d);
      }
    };

    for (size_t i = 0; i + 1 < path.size(); i++) {
      const Point d = path[i + 1] - path[i];

      if (d.x != 0 && d.y != 0) {
        add_delta({d.x, 0});
        add_delta({0, d.y});
      } else {
        add_delta(d);
      }
    }

    int total_len = 0;

    for (const Point d : deltas) {
      total_len += d.x;
      total_len += abs(d.y);
    }

    cout << total_len << endl;

#ifndef DEV
    cout << deltas.size() << endl;

    for (const Point d : deltas) {
      cout << d.x << ' ' << d.y << endl;
    }
#endif
  }
}

• Subtask 1: 100 / 100