Submission #1306652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306652		chrisvilches	Walk (CEOI06_walk)	C++20	0 / 100	392 ms	47928 KiB

walk

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

struct Point {
  int x, 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); }

  bool operator==(const Point p) const { return x == p.x && y == p.y; }
};

ostream& operator<<(ostream& os, const Point p) {
  return os << "(" << p.x << ", " << p.y << ")";
}

string polygon_to_str(const vector<Point>& polygon) {
  stringstream ss;
  ss << fixed << setprecision(6);
  ss << "polygon(";
  for (size_t i = 0; i < polygon.size(); i++) {
    if (i > 0) ss << ", ";
    ss << polygon[i];
  }
  ss << ")";
  return ss.str();
}

struct Segment {
  Point p, q;

  string to_desmos() const {
    stringstream ss;
    ss << fixed << setprecision(6) << "\\left(\\left(1-t\\right)\\cdot" << p.x + 0.5
       << "+t\\cdot" << q.x + 0.5 << ",\\left(1-t\\right)\\cdot" << p.y + 0.5
       << "+t\\cdot" << q.y + 0.5 << "\\right)";
    return ss.str();
  }
};

int main() {
  int n;
  Point dest;
  while (cin >> dest.x >> dest.y >> n) {
    // cerr << endl << "---------------------------------------------" << endl << endl;
    vector<tuple<int, int, int, int>> events;

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

      // TODO: Maybe I can use each y independently on each event (no need to have both in
      // one item). I think I need to remove in the range, so I can't do that!!!
      events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
      events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);

      // vector<Point> poly;
      // poly.emplace_back(x1, y1);
      // poly.emplace_back(x2 + 1, y1);
      // poly.emplace_back(x2 + 1, y2 + 1);
      // poly.emplace_back(x1, y2 + 1);
      //
      // cerr << polygon_to_str(poly) << endl;
    }

    // TODO: what should the type be in this event????

    const int DEST = 2;
    events.emplace_back(dest.x, DEST, dest.y, dest.y);

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

    map<int, Point> m;

    map<Point, Point> prev_point;

    const int inf = 1e7;

    m[0] = {0, 0};
    // TODO: Maybe this will overflow in some cases.
    // TODO: This data is weird lmao
    m[INT_MIN] = {0, -inf};
    m[INT_MAX] = {0, inf};

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

    const auto update = [&](const int x, const int y) {
      const Point p{x, y};

      if (prev_point.count(p)) return;

      const auto it0 = m.lower_bound(y);
      const auto it1 = it0->first == y ? it0 : prev(it0);

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

        const int alt = dist[point] + p.dist(point);
        assert(alt >= 0);

        if (!dist.count(p) || dist[p] > alt) {
          prev_point[p] = point;
          dist[p] = alt;
        }
      }

      m[p.y] = p;
    };

    for (const auto& [x, type, y1, y2] : events) {
      // cerr << format("x: {}, type: {}, y = [{}, {}]", x, type, y1, y2) << endl;
      // cerr << "type: " << type << endl;

      // TODO: I'm not using the `type` lol
      if (type == DEST) {
        update(x, y1);
      } else {
        update(x, y1);
        update(x, y2);
      }

      // TODO: I think I have to remove the items between y1 and y2???????
      while (true) {
        const auto it = m.lower_bound(y1 + 1);
        if (it == m.end()) break;
        if (y2 - 1 <= it->first) break;
        m.erase(it);
      }
    }

    vector<Point> path;

    Point curr = dest;

    while (!(curr == Point{0, 0})) {
      path.emplace_back(curr);
      if (!prev_point.count(curr)) {
        cerr << "not found!!!!!!!!!!!!!!! prev of : " << curr << endl;
        break;
      }
      if (curr == prev_point[curr]) {
        cerr << "equal!!!!!!!!!!!!!! " << curr << endl;
        break;
      }
      curr = prev_point[curr];
    }

    path.emplace_back(curr);

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

    vector<Point> fixed_path;
    for (size_t i = 0; i < path.size() - 1; i++) {
      fixed_path.emplace_back(path[i]);
      if (path[i].x < path[i + 1].x) {
        fixed_path.emplace_back(path[i + 1].x, path[i].y);
      }
    }
    fixed_path.emplace_back(path.back());

    int total_len = 0;
    for (size_t i = 0; i < path.size() - 1; i++) {
      total_len += path[i].dist(path[i + 1]);
    }

    int another = 0;
    for (size_t i = 0; i < fixed_path.size() - 1; i++) {
      const Point p = fixed_path[i];
      const Point q = fixed_path[i + 1];
      another += p.dist(q);
      // cerr << Segment{p, q}.to_desmos() << endl;
    }
    assert(total_len == another);

    cout << total_len << endl;
  }
}

• Subtask 1: 0 / 100