Submission #1037264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037264		shmax	Sky Walking (IOI19_walk)	C++17	24 / 100	4072 ms	606664 KiB

walk

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

using namespace std;
using i32 = int;
#define int long long
#define all(x) x.begin(), x.end()
#define len(x) (int)(x.size())
#define inf 1000'000'000'000'000'000LL
#define bit(x, i) (((x) >> i) & 1)

template<typename T>
using vec = vector<T>;


int min_distance(std::vector<i32> x, std::vector<i32> h, std::vector<i32> L,
                 std::vector<i32> R, std::vector<i32> Y, i32 s, i32 e) {
    int n = len(x);
    set<int> exist;
    for (int i = 0; i < n; i++)
        exist.insert(i);
    struct line {
        int l, r, h;
    };
    vec<line> lines;
    for (int i = 0; i < len(L); i++) {
        lines.push_back({L[i], R[i], Y[i]});
    }
    sort(all(lines), [&](line a, line b) {
        return a.h < b.h;
    });
    vec<int> buildings(n);
    iota(all(buildings), 0);
    sort(all(buildings), [&](int i, int j) {
        return h[i] < h[j];
    });
    int ptr = 0;
    map<pair<int, int>, int> ids;
    int cur_id = 0;
    vec<vec<pair<int, int>>> g;
    auto create = [&](pair<int, int> a) {
        if (!ids.count(a)) {
            ids[a] = cur_id++;
            g.emplace_back();
        }
    };

    auto add_edge = [&](pair<int, int> f1, pair<int, int> f2) {
        int v = ids[f1];
        int u = ids[f2];
        g[v].push_back({u, abs(f1.first - f2.first) + abs(f1.second - f2.second)});
        g[u].push_back({v, abs(f1.first - f2.first) + abs(f1.second - f2.second)});
    };
    vec<vec<pair<int, int>>> points_build(n);
    for (auto [l, r, y]: lines) {
        while (ptr < n and h[buildings[ptr]] < y) {
            exist.erase(buildings[ptr]);
            ptr++;
        }
        vec<pair<int, int>> points;
        auto ptr = exist.lower_bound(l);
        while (ptr != exist.end() and *ptr <= r) {
            create({x[*ptr], y});
            points.push_back({x[*ptr], y});
            points_build[*ptr].push_back({x[*ptr], y});
            ptr++;
        }
        for (int i = 1; i < len(points); i++) {
            add_edge(points[i - 1], points[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        create({x[i], 0});
        points_build[i].push_back({x[i], 0});
        sort(all(points_build[i]));
        for (int j = 1; j < len(points_build[i]); j++) {
            add_edge(points_build[i][j - 1], points_build[i][j]);
        }
    }

    int m = len(ids);
    vec<int> dist(m, inf);
    dist[ids[{x[s], 0}]] = 0;
    priority_queue<pair<int, int>, vec<pair<int, int>>, greater<>> pq;
    pq.push({0, ids[{x[s], 0}]});
    while (!pq.empty()) {
        auto [dst, v] = pq.top();
        pq.pop();
        if (dst > dist[v]) continue;
        for (auto [u, w]: g[v]) {
            if (dist[u] > dst + w) {
                dist[u] = dst + w;
                pq.push({dist[u], u});
            }
        }
    }
    if (dist[ids[{x[e], 0}]] == inf) dist[ids[{x[e], 0}]] = -1;
    return dist[ids[{x[e], 0}]];
}

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