oj.uz

Submission #223804

# Submission time Handle Problem Language Result Execution time Memory
223804 2020-04-16T13:35:19 Z rama_pang Sky Walking (IOI19_walk) C++14
100 / 100
 3128 ms 233496 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 807 ms 81184 KB Output is correct
4 Correct 802 ms 83452 KB Output is correct
5 Correct 541 ms 64844 KB Output is correct
6 Correct 551 ms 62256 KB Output is correct
7 Correct 535 ms 65488 KB Output is correct
8 Correct 847 ms 87492 KB Output is correct
9 Correct 705 ms 77204 KB Output is correct
10 Correct 870 ms 87552 KB Output is correct
11 Correct 608 ms 63740 KB Output is correct
12 Correct 476 ms 43940 KB Output is correct
13 Correct 818 ms 86404 KB Output is correct
14 Correct 648 ms 59140 KB Output is correct
15 Correct 530 ms 49168 KB Output is correct
16 Correct 409 ms 47120 KB Output is correct
17 Correct 396 ms 44796 KB Output is correct
18 Correct 1384 ms 124040 KB Output is correct
19 Correct 28 ms 3588 KB Output is correct
20 Correct 325 ms 33372 KB Output is correct
21 Correct 395 ms 46068 KB Output is correct
22 Correct 394 ms 43784 KB Output is correct
23 Correct 881 ms 75592 KB Output is correct
24 Correct 376 ms 45476 KB Output is correct
25 Correct 379 ms 45032 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19756 KB Output is correct
2 Correct 1096 ms 105688 KB Output is correct
3 Correct 1204 ms 110440 KB Output is correct
4 Correct 1285 ms 114592 KB Output is correct
5 Correct 1769 ms 124944 KB Output is correct
6 Correct 1661 ms 116244 KB Output is correct
7 Correct 575 ms 58368 KB Output is correct
8 Correct 407 ms 43788 KB Output is correct
9 Correct 1720 ms 119032 KB Output is correct
10 Correct 623 ms 65164 KB Output is correct
11 Correct 50 ms 4504 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19756 KB Output is correct
2 Correct 1096 ms 105688 KB Output is correct
3 Correct 1204 ms 110440 KB Output is correct
4 Correct 1285 ms 114592 KB Output is correct
5 Correct 1769 ms 124944 KB Output is correct
6 Correct 1661 ms 116244 KB Output is correct
7 Correct 575 ms 58368 KB Output is correct
8 Correct 407 ms 43788 KB Output is correct
9 Correct 1720 ms 119032 KB Output is correct
10 Correct 623 ms 65164 KB Output is correct
11 Correct 50 ms 4504 KB Output is correct
12 Correct 1211 ms 109988 KB Output is correct
13 Correct 1188 ms 114576 KB Output is correct
14 Correct 1836 ms 124760 KB Output is correct
15 Correct 966 ms 87164 KB Output is correct
16 Correct 1102 ms 92484 KB Output is correct
17 Correct 1284 ms 115120 KB Output is correct
18 Correct 1142 ms 87344 KB Output is correct
19 Correct 1190 ms 92516 KB Output is correct
20 Correct 740 ms 57644 KB Output is correct
21 Correct 170 ms 8752 KB Output is correct
22 Correct 760 ms 86692 KB Output is correct
23 Correct 668 ms 80716 KB Output is correct
24 Correct 486 ms 51228 KB Output is correct
25 Correct 599 ms 70840 KB Output is correct
26 Correct 381 ms 37936 KB Output is correct
27 Correct 1800 ms 121820 KB Output is correct
28 Correct 1006 ms 112464 KB Output is correct
29 Correct 1721 ms 116108 KB Output is correct
30 Correct 622 ms 57984 KB Output is correct
31 Correct 1716 ms 117496 KB Output is correct
32 Correct 494 ms 54056 KB Output is correct
33 Correct 442 ms 48776 KB Output is correct
34 Correct 665 ms 65784 KB Output is correct
35 Correct 573 ms 63296 KB Output is correct
36 Correct 442 ms 50048 KB Output is correct
37 Correct 420 ms 46044 KB Output is correct
38 Correct 399 ms 43780 KB Output is correct
39 Correct 901 ms 75688 KB Output is correct
40 Correct 393 ms 45480 KB Output is correct
41 Correct 374 ms 44944 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 807 ms 81184 KB Output is correct
21 Correct 802 ms 83452 KB Output is correct
22 Correct 541 ms 64844 KB Output is correct
23 Correct 551 ms 62256 KB Output is correct
24 Correct 535 ms 65488 KB Output is correct
25 Correct 847 ms 87492 KB Output is correct
26 Correct 705 ms 77204 KB Output is correct
27 Correct 870 ms 87552 KB Output is correct
28 Correct 608 ms 63740 KB Output is correct
29 Correct 476 ms 43940 KB Output is correct
30 Correct 818 ms 86404 KB Output is correct
31 Correct 648 ms 59140 KB Output is correct
32 Correct 530 ms 49168 KB Output is correct
33 Correct 409 ms 47120 KB Output is correct
34 Correct 396 ms 44796 KB Output is correct
35 Correct 1384 ms 124040 KB Output is correct
36 Correct 28 ms 3588 KB Output is correct
37 Correct 325 ms 33372 KB Output is correct
38 Correct 395 ms 46068 KB Output is correct
39 Correct 394 ms 43784 KB Output is correct
40 Correct 881 ms 75592 KB Output is correct
41 Correct 376 ms 45476 KB Output is correct
42 Correct 379 ms 45032 KB Output is correct
43 Correct 147 ms 19756 KB Output is correct
44 Correct 1096 ms 105688 KB Output is correct
45 Correct 1204 ms 110440 KB Output is correct
46 Correct 1285 ms 114592 KB Output is correct
47 Correct 1769 ms 124944 KB Output is correct
48 Correct 1661 ms 116244 KB Output is correct
49 Correct 575 ms 58368 KB Output is correct
50 Correct 407 ms 43788 KB Output is correct
51 Correct 1720 ms 119032 KB Output is correct
52 Correct 623 ms 65164 KB Output is correct
53 Correct 50 ms 4504 KB Output is correct
54 Correct 1211 ms 109988 KB Output is correct
55 Correct 1188 ms 114576 KB Output is correct
56 Correct 1836 ms 124760 KB Output is correct
57 Correct 966 ms 87164 KB Output is correct
58 Correct 1102 ms 92484 KB Output is correct
59 Correct 1284 ms 115120 KB Output is correct
60 Correct 1142 ms 87344 KB Output is correct
61 Correct 1190 ms 92516 KB Output is correct
62 Correct 740 ms 57644 KB Output is correct
63 Correct 170 ms 8752 KB Output is correct
64 Correct 760 ms 86692 KB Output is correct
65 Correct 668 ms 80716 KB Output is correct
66 Correct 486 ms 51228 KB Output is correct
67 Correct 599 ms 70840 KB Output is correct
68 Correct 381 ms 37936 KB Output is correct
69 Correct 1800 ms 121820 KB Output is correct
70 Correct 1006 ms 112464 KB Output is correct
71 Correct 1721 ms 116108 KB Output is correct
72 Correct 622 ms 57984 KB Output is correct
73 Correct 1716 ms 117496 KB Output is correct
74 Correct 494 ms 54056 KB Output is correct
75 Correct 442 ms 48776 KB Output is correct
76 Correct 665 ms 65784 KB Output is correct
77 Correct 573 ms 63296 KB Output is correct
78 Correct 442 ms 50048 KB Output is correct
79 Correct 420 ms 46044 KB Output is correct
80 Correct 399 ms 43780 KB Output is correct
81 Correct 901 ms 75688 KB Output is correct
82 Correct 393 ms 45480 KB Output is correct
83 Correct 374 ms 44944 KB Output is correct
84 Correct 137 ms 15812 KB Output is correct
85 Correct 1327 ms 118176 KB Output is correct
86 Correct 2413 ms 176588 KB Output is correct
87 Correct 163 ms 11368 KB Output is correct
88 Correct 208 ms 12016 KB Output is correct
89 Correct 154 ms 11364 KB Output is correct
90 Correct 48 ms 5672 KB Output is correct
91 Correct 7 ms 512 KB Output is correct
92 Correct 54 ms 4524 KB Output is correct
93 Correct 542 ms 41948 KB Output is correct
94 Correct 185 ms 9008 KB Output is correct
95 Correct 790 ms 92260 KB Output is correct
96 Correct 670 ms 81248 KB Output is correct
97 Correct 600 ms 60368 KB Output is correct
98 Correct 627 ms 73844 KB Output is correct
99 Correct 3128 ms 233496 KB Output is correct
100 Correct 1242 ms 114388 KB Output is correct
101 Correct 2091 ms 153416 KB Output is correct
102 Correct 668 ms 58560 KB Output is correct
103 Correct 490 ms 53084 KB Output is correct
104 Correct 465 ms 48648 KB Output is correct
105 Correct 754 ms 61608 KB Output is correct
106 Correct 564 ms 54412 KB Output is correct
107 Correct 723 ms 59508 KB Output is correct
108 Correct 89 ms 9048 KB Output is correct
109 Correct 1286 ms 88856 KB Output is correct
110 Correct 1038 ms 113708 KB Output is correct
111 Correct 1043 ms 115164 KB Output is correct
112 Correct 555 ms 61172 KB Output is correct
113 Correct 531 ms 60408 KB Output is correct