Submission #270037

#	Time	Username	Problem	Language	Result	Execution time	Memory
270037		hamerin	Sky Walking (IOI19_walk)	C++17	100 / 100	1926 ms	199204 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const i64 inf = numeric_limits<i64>::max() / 3;

vector<i64> dijkstra(int sv, const vector<vector<pli>> &adj) {
    vector<i64> dist(adj.size(), inf);
    priority_queue<pli, vector<pli>, greater<>> pq;
    dist[sv] = 0;
    pq.emplace(0, sv);

    while (!pq.empty()) {
        auto [W, u] = pq.top();
        pq.pop();

        if (W > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > W + w) {
                pq.emplace(W + w, v);
                dist[v] = W + w;
            }
        }
    }

    return dist;
}


class Edge {
   public:
    pair<int, i64> u, v;
    i64 w;

    Edge() = default;
    Edge(decltype(u) _u, decltype(v) _v, decltype(w) _w) {
        if (_u > _v) swap(_u, _v);
        u = _u, v = _v, w = _w;
    }
};

bool edgeCompare(const Edge &lhs, const Edge &rhs) {
    return lhs.u == rhs.u ? lhs.v < rhs.v : lhs.u < rhs.u;
}

bool edgeEqual(const Edge &lhs, const Edge &rhs) {
    return lhs.u == rhs.u && lhs.v == rhs.v;
}


namespace Helper {
    bool inRange(int x, int s, int e) { return s <= x && x <= e; }

    template <typename T>
    int findIndex(const vector<T> &vec, T &&toFind) {
        return lower_bound(iterall(vec), toFind) - vec.begin();
    }

    template <typename T>
    int findIndex(const vector<T> &vec, const T &toFind) {
        return lower_bound(iterall(vec), toFind) - vec.begin();
    }
}  // namespace Helper

const bool DEBUG = false;

i64 min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
                 vector<int> y, int s, int g) {
    int N = x.size();
    int M = l.size();

    vector<tuple<i64, int, int>> horizontalLines;
    for (int i = 0; i < M; i++) horizontalLines.emplace_back(y[i], l[i], r[i]);
    sort(iterall(horizontalLines));

    vector<pair<i64, int>> verticalLines;
    for (int i = 0; i < N; i++) verticalLines.emplace_back(h[i], i);
    sort(iterall(verticalLines), greater<>());


    set<int> verticalSet;
    for (int i = 0; i < N; i++) verticalSet.emplace(i);

    vector<Edge> edge;
    vector<pair<int, i64>> vertex;
    int vertNum = 2;

    vertex.emplace_back(s, 0);
    vertex.emplace_back(g, 0);

    set<pi> adjacentForwardLook = {pi(s, 0), pi(g, 1)};  // y Increasing
    vector<vector<int>> horizontalVertex(M);
    vector<vector<int>> horizontalVertexAppended(M);

    auto appendVertex = [&](int x, int i) mutable {
        vertex.emplace_back(x, get<0>(horizontalLines[i]));
        adjacentForwardLook.emplace(x, vertNum);
        horizontalVertex[i].emplace_back(vertNum);
        horizontalVertexAppended[i].emplace_back(vertNum);
        ++vertNum;
    };


    for (int i = 0; i < M; i++) {
        auto [Y, L, R] = horizontalLines[i];

        while (!verticalLines.empty() && verticalLines.back().first < Y) {
            verticalSet.erase(verticalLines.back().second);
            verticalLines.pop_back();
        }

        {
            auto siter = adjacentForwardLook.lower_bound({L, 0});
            auto eiter = adjacentForwardLook.upper_bound({R, vertNum});
            for (auto it = siter; it != eiter; it++) {
                if (Y > h[it->first]) continue;

                vertex.emplace_back(it->first, Y);
                edge.emplace_back(Edge(vertex[it->second], vertex[vertNum],
                                       Y - vertex[it->second].second));
                horizontalVertexAppended[i].emplace_back(vertNum);
                ++vertNum;
            }
            adjacentForwardLook.erase(siter, eiter);
        }

        appendVertex(L, i);
        appendVertex(R, i);

        if (Helper::inRange(s, L, R)) {
            if (Y <= h[s]) {
                appendVertex(s, i);
            } else {
                auto iter = verticalSet.lower_bound(s);
                if (iter != verticalSet.end() && Helper::inRange(*iter, L, R)) {
                    appendVertex(*iter, i);
                }

                --iter;
                if (iter != verticalSet.end() && Helper::inRange(*iter, L, R)) {
                    appendVertex(*iter, i);
                }
            }
        }

        if (Helper::inRange(g, L, R)) {
            if (Y <= h[g]) {
                appendVertex(g, i);
            } else {
                auto iter = verticalSet.lower_bound(g);
                if (iter != verticalSet.end() && Helper::inRange(*iter, L, R)) {
                    appendVertex(*iter, i);
                }

                --iter;
                if (iter != verticalSet.end() && Helper::inRange(*iter, L, R)) {
                    appendVertex(*iter, i);
                }
            }
        }
    }


    set<pi> adjacentBackwardLook;
    for (int i = M - 1; i >= 0; i--) {
        auto [Y, L, R] = horizontalLines[i];

        auto siter = adjacentBackwardLook.lower_bound({L, 0});
        auto eiter = adjacentBackwardLook.upper_bound({R, vertNum});
        for (auto it = siter; it != eiter; it++) {
            vertex.emplace_back(it->first, Y);
            edge.emplace_back(Edge(vertex[it->second], vertex[vertNum],
                                   vertex[it->second].second - Y));
            horizontalVertexAppended[i].emplace_back(vertNum);
            ++vertNum;
        }
        adjacentBackwardLook.erase(siter, eiter);

        for (auto vn : horizontalVertex[i]) {
            adjacentBackwardLook.emplace(vertex[vn].first, vn);
        }
    }


    for (int i = 0; i < M; i++) {
        auto &hvX = horizontalVertexAppended[i];

        sort(iterall(hvX), [&vertex](int l, int r) {
            return vertex[l].first < vertex[r].first;
        });

        hvX.erase(unique(iterall(hvX),
                         [&vertex](int l, int r) {
                             return vertex[l].first == vertex[r].first;
                         }),
                  hvX.end());

        for (int j = 0; j < hvX.size() - 1; j++) {
            int lvn = hvX[j];
            int rvn = hvX[j + 1];

            edge.emplace_back(
                Edge(vertex[lvn], vertex[rvn],
                     x[vertex[rvn].first] - x[vertex[lvn].first]));
        }
    }


    sort(iterall(vertex));
    vertex.erase(unique(iterall(vertex)), vertex.end());
    sort(iterall(edge), edgeCompare);
    edge.erase(unique(iterall(edge), edgeEqual), edge.end());

    int V = vertex.size();
    vector<vector<pli>> Graph(V);

    for (auto ed : edge) {
        auto uIndex = Helper::findIndex(vertex, ed.u);
        auto vIndex = Helper::findIndex(vertex, ed.v);

        Graph[uIndex].emplace_back(vIndex, ed.w);
        Graph[vIndex].emplace_back(uIndex, ed.w);
    }

    if (DEBUG) {
        for (auto [x, y] : vertex) cout << x << " " << y << endl;
        for (auto ed : edge) {
            cout << ed.u.first << " " << ed.u.second << " " << ed.v.first << " "
                 << ed.v.second << " " << ed.w << endl;
        }
    }

    int startVertex = Helper::findIndex(vertex, {s, 0});
    int endVertex = Helper::findIndex(vertex, {g, 0});

    i64 ret = dijkstra(startVertex, Graph)[endVertex];
    if (ret >= inf) ret = -1;

    return ret;
}

Compilation message (stderr)

walk.cpp: In function 'i64 min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:213:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         for (int j = 0; j < hvX.size() - 1; j++) {
      |                         ~~^~~~~~~~~~~~~~~~

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