제출 #223804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223804		rama_pang	Sky Walking (IOI19_walk)	C++14	100 / 100	3128 ms	233496 KiB

walk

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

class Graph {
 private:
  struct edge_t {
    int v;
    long long w;
    edge_t() {}
    edge_t(int v, long long w) : v(v), w(w) {}
    bool operator < (const edge_t &o) const { return w > o.w; }
  };

  vector<vector<edge_t>> adj;

 public:
  Graph() {}

  int AddVertex() {
    adj.emplace_back();
    return (int) adj.size() - 1;
  }

  void AddEdge(int u, int v, long long w) {
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  long long Dijkstra(int s, int g) {
    priority_queue<edge_t> pq;
    vector<long long> dist(adj.size(), -1);
    pq.emplace(s, 0);
    dist[s] = 0;

    while (!pq.empty()) {
      int u = pq.top().v;
      long long d = pq.top().w;
      pq.pop();
      if (dist[u] != d) continue;
      for (auto e : adj[u]) {
        if (dist[e.v] == -1 || dist[e.v] > dist[u] + e.w) {
          dist[e.v] = dist[u] + e.w;
          pq.emplace(e.v, dist[e.v]);
        }
      }
    }

    return dist[g];
  }
};

struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  bool operator < (const Point &o) const { return make_pair(x, y) < make_pair(o.x, o.y); }
  bool operator > (const Point &o) const { return make_pair(x, y) > make_pair(o.x, o.y); }
  bool operator == (const Point &o) const { return x == o.x && y == o.y; }
};

class Planar {
 private:
  Graph G;
  map<Point, int> id;

 public:
  Planar() {}

  void AddVertex(Point p) {
    if (!id.count(p)) id.emplace(p, G.AddVertex());
  }

  void AddEdge(Point a, Point b) {
    if (a == b) return;
    AddVertex(a), AddVertex(b);
    G.AddEdge(id[a], id[b], abs(a.x - b.x) + abs(a.y - b.y));
  }

  long long Dijkstra(Point s, Point g) {
    AddVertex(s), AddVertex(g);
    return G.Dijkstra(id[s], id[g]);
  }
};

long long min_distance(vector<int> x, vector<int> h, vector<int> l, 
                       vector<int> r, vector<int> y, int s, int g) {
  Planar G;

  auto SplitSkywalk = [&](int p) { // Split skywalks that passes over p into separate parts
    struct event_t {
      int t; // type 0 = skywalk, 1 = building
      int id;
      int h, l, r;
      event_t() {}
      event_t(int t, int id, int h, int l, int r) : t(t), id(id), h(h), l(l), r(r) {}
    };

    int n = x.size(), m = y.size();
    vector<int> new_l;
    vector<int> new_r;
    vector<int> new_y;

    vector<event_t> events; 
    for (int i = 0; i < m; i++) {
      events.emplace_back(0, i, y[i], l[i], r[i]);
    }
    for (int i = 0; i < n; i++) {
      events.emplace_back(1, i, h[i], i, i);
    }
    
    set<int> active; // active buildings
    for (int i = 0; i < n; i++) {
      active.emplace(i);
    }

    sort(begin(events), end(events), [&](const event_t &a, const event_t &b) {
      return make_pair(a.h, a.t) < make_pair(b.h, b.t);
    });

    for (auto event : events) {
      if (event.t == 0) { // skywalk
        if (event.r < p || p < event.l) { // doesn't pass over p
          new_y.emplace_back(event.h);
          new_l.emplace_back(event.l);
          new_r.emplace_back(event.r);
          continue;
        }

        auto lb = active.lower_bound(p);
        auto ub = active.upper_bound(p);

        int on_left = (ub == begin(active) ? -1 : *prev(ub));
        int on_right = (lb == end(active) ? -1 : *lb);

        if (event.l <= on_left && on_right <= event.r) {
          new_y.emplace_back(event.h);
          new_l.emplace_back(event.l);
          new_r.emplace_back(on_left);

          new_y.emplace_back(event.h);
          new_l.emplace_back(on_left);
          new_r.emplace_back(on_right);
          
          new_y.emplace_back(event.h);
          new_l.emplace_back(on_right);
          new_r.emplace_back(event.r);
        }
      } else { // building
        active.erase(event.id);
      }
    }

    l = new_l, r = new_r, y = new_y;
  };
  
  auto BuildGraph = [&]() { // For each endpoint of skywalks, add vertices on the skywalk above and below the current one
    l.emplace_back(s);
    r.emplace_back(s);
    y.emplace_back(0);

    l.emplace_back(g);
    r.emplace_back(g);
    y.emplace_back(0);

    int n = x.size(), m = y.size();
    vector<vector<pair<int, int>>> events(n); // (height, id)
    vector<int> last_point(m); // last point added on the i-th skywalk

    for (int i = 0; i < m; i++) {
      events[l[i]].emplace_back(+y[i], i); // add new skywalk starting from at l[i]
      events[r[i]].emplace_back(-y[i], i); // delete skywalks ending at r[i]
      last_point[i] = x[l[i]];
    }

    set<pair<int, int>> ys; // (height, id)
    ys.emplace(-1, -1);

    for (int i = 0; i < n; i++) {
      sort(begin(events[i]), end(events[i]), greater<pair<int, int>>());
      for (auto event : events[i]) {
        int y = abs(event.first), id = event.second;

        auto lb = ys.lower_bound({y, -1});
        auto ub = ys.upper_bound({y, m});
        
        int above = (ub == end(ys) ? -1 : ub->first);
        int id_above = (ub == end(ys) ? -1 : ub->second);
        
        int below = (lb == begin(ys) ? -1 : prev(lb)->first);
        int id_below = (lb == begin(ys) ? -1 : prev(lb)->second);
        
        if (above != -1 && above <= h[i]) {
          G.AddEdge(Point(x[i], y), Point(x[i], above));
          G.AddEdge(Point(last_point[id_above], above), Point(x[i], above));
          last_point[id_above] = x[i];
        }
        
        if (below != -1) {
          G.AddEdge(Point(x[i], y), Point(x[i], below));
          G.AddEdge(Point(last_point[id_below], below), Point(x[i], below));
          last_point[id_below] = x[i];
        }

        if (event.first > 0) {
          ys.emplace(y, id);
        } else if (event.first < 0) {
          G.AddEdge(Point(x[i], y), Point(last_point[id], y));
          ys.erase({y, id});
        }
      }
    }
  };

  SplitSkywalk(s);
  SplitSkywalk(g);
  BuildGraph();

  return G.Dijkstra(Point(x[s], 0), Point(x[g], 0));
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43