Submission #1306685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306685		chrisvilches	Walk (CEOI06_walk)	C++20	100 / 100	339 ms	47360 KiB

walk

#include <bits/stdc++.h>
using namespace std;

struct Point {
  int x, y;
  Point operator-(const Point p) const { return {x - p.x, y - p.y}; }
  void operator+=(const Point p) {
    x += p.x;
    y += p.y;
  }
  bool operator<(const Point p) const { return x < p.x || (x == p.x && y < p.y); }
  int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
};

const int INF = 1e8;

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);
      assert(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, Point> m;
    map<Point, Point> parent;

    m[0] = {0, 0};
    m[-INF] = {0, -INF};
    m[INF] = {0, INF};

    map<Point, int> dist;
    dist[{0, 0}] = 0;

    const auto update = [&](const Point p) {
      const auto it0 = m.lower_bound(p.y);
      const auto it1 = it0->first == p.y ? it0 : prev(it0);
      // TODO: There's a weird thing here... if I do it1 = prev(it0)
      // (i.e. always use prev), it will get WA answers. It should still
      // work and ignore the one that's not useful.

      for (const auto it : {it0, it1}) {
        const Point prev = it->second;
        const int new_dist = dist[prev] + p.dist(prev);

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

      m[p.y] = p;
    };

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

      while (true) {
        const auto it = m.lower_bound(y1 + 1);
        if (y2 <= it->first) break;
        m.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() += d;
      } 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) {
        // TODO: If I swap the order of these two lines, the judge will say
        // "path intersects a building". Why? could it be because of the order
        // and/or direction of the sweep line???
        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;

    cout << deltas.size() << endl;

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

• Subtask 1: 100 / 100