Submission #612014

#	Time	Username	Problem	Language	Result	Execution time	Memory
612014		KoD	Sky Walking (IOI19_walk)	C++17	100 / 100	2053 ms	193272 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<T>>;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int src, int dst) {
    const int N = (int)X.size();
    for (const int pivot : {src, dst}) {
        const int M = (int)Y.size();
        vector<pair<int, int>> left, right;
        for (int i = pivot; i >= 0; --i) {
            if (left.empty() or left.back().first < H[i]) {
                left.emplace_back(H[i], i);
            }
        }
        for (int i = pivot; i < N; ++i) {
            if (right.empty() or right.back().first < H[i]) {
                right.emplace_back(H[i], i);
            }
        }
        for (int i = 0; i < M; ++i) {
            if (L[i] < pivot and pivot < R[i]) {
                const int a = std::lower_bound(left.begin(), left.end(), pair(Y[i], 0))->second;
                const int b = std::lower_bound(right.begin(), right.end(), pair(Y[i], 0))->second;
                L.push_back(L[i]);
                R.push_back(a);
                Y.push_back(Y[i]);
                L.push_back(b);
                R.push_back(R[i]);
                Y.push_back(Y[i]);
                L[i] = a;
                R[i] = b;
            }
        }
    }
    vector<vector<pair<int, int>>> graph(N);
    const auto add_vertex = [&] {
        graph.emplace_back();
        return (int)graph.size() - 1;
    };
    const auto add_edge = [&](const int u, const int v, const int c) {
        graph[u].emplace_back(v, c);
        graph[v].emplace_back(u, c);
    };
    vector<vector<pair<int, int>>> vertices(N);
    for (int i = 0; i < N; ++i) {
        vertices[i].emplace_back(0, i);
    }
    const int M = (int)Y.size();
    vector<int> order(M);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](const int i, const int j) {
        return Y[i] < Y[j];
    });
    for (int step = 0; step < 2; ++step) {
        std::set<int> remain;
        for (int i = 0; i < N; ++i) {
            remain.insert(i);
        }
        for (const int e : order) {
            if (L[e] == R[e]) {
                continue;
            }
            vector<int> list;
            list.push_back(L[e]);
            remain.insert(L[e]);
            for (auto itr = remain.upper_bound(L[e]); itr != remain.end() and *itr < R[e]; itr = remain.erase(itr)) {
                if (Y[e] <= H[*itr]) {
                    list.push_back(*itr);
                }
            }
            list.push_back(R[e]);
            remain.insert(R[e]);
            const int n = (int)list.size();
            vector<int> id(n);
            for (int i = 0; i < n; ++i) {
                id[i] = add_vertex();
                vertices[list[i]].emplace_back(Y[e], id[i]);
            }
            for (int i = 0; i + 1 < n; ++i) {
                add_edge(id[i], id[i + 1], X[list[i + 1]] - X[list[i]]);
            }
        }
        std::reverse(order.begin(), order.end());
    }
    for (auto& vec : vertices) {
        std::sort(vec.begin(), vec.end());
        const int n = (int)vec.size();
        for (int i = 0; i + 1 < n; ++i) {
            add_edge(vec[i].second, vec[i + 1].second, vec[i + 1].first - vec[i].first);
        }
    }
    vector<ll> dist(graph.size(), std::numeric_limits<ll>::max());
    min_heap<pair<ll, int>> heap;
    const auto push = [&](const int u, const ll d) {
        if (dist[u] > d) {
            dist[u] = d;
            heap.emplace(d, u);
        }
    };
    push(src, 0);
    while (!heap.empty()) {
        const auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) {
            continue;
        }
        for (const auto& [v, c] : graph[u]) {
            push(v, d + c);
        }
    }
    const ll ret = dist[dst];
    return ret == std::numeric_limits<ll>::max() ? -1 : ret;
}

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