Submission #792280

#	Time	Username	Problem	Language	Result	Execution time	Memory
792280		skittles1412	Sky Walking (IOI19_walk)	C++17	24 / 100	3110 ms	1048576 KiB

walk

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template <typename T>
struct Comp {
    map<T, int> mp;

    int operator()(const T& t) {
        auto [it, inserted] = mp.emplace(t, -1);
        if (inserted) {
            it->second = sz(mp) - 1;
        }
        return it->second;
    }
};

template <typename S>
long dijkstra(const vector<tuple<S, S, long>>& edges, S src, S dest) {
    dbg("A");
    int n = 2 * sz(edges) + 10;

    Comp<S> comp;
    vector<pair<int, long>> graph[n];

    for (auto& [u, v, w] : edges) {
        int cu = comp(u), cv = comp(v);
        graph[cu].emplace_back(cv, w);
        graph[cv].emplace_back(cu, w);
    }

    long dist[n];
    memset(dist, 0x3f, sizeof(dist));

    min_pq<pair<long, int>> pq;
    auto push = [&](int u, long d) -> void {
        if (d >= dist[u]) {
            return;
        }
        dist[u] = d;
        pq.emplace(d, u);
    };

    int c_src = comp(src), c_dest = comp(dest);

    push(c_src, 0);

    while (sz(pq)) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == c_dest) {
            return d;
        }
        if (d != dist[u]) {
            continue;
        }

        for (auto& [v, w] : graph[u]) {
            push(v, d + w);
        }
    }

    return -1;
}

namespace s1 {

long solve(vector<pair<int, int>> arr,
           vector<array<int, 3>> walk,
           int src,
           int dest) {
    src = arr[src].first;
    dest = arr[dest].first;

    map<int, vector<pair<int, int>>> evts;
    for (auto& [x, h] : arr) {
        evts[-h].emplace_back(x, -1);
    }
    for (auto& [ql, qr, h] : walk) {
        ql = arr[ql].first;
        qr = arr[qr].first;
        evts[-h].emplace_back(ql, qr);
    }

    vector<array<int, 3>> d_walk;
    {
        set<int> pos;
        for (auto& [nh, ev] : evts) {
            int h = -nh;

            for (auto& [x, ty] : ev) {
                if (ty == -1) {
                    dbg(h, x);
                    pos.insert(x);
                }
            }

            for (auto& [ql, qr] : ev) {
                if (qr == -1) {
                    continue;
                }
                dbg(h, ql, qr);

                auto it = pos.lower_bound(ql);
                while (true) {
                    int cl = *it;
                    ++it;
                    int cr = *it;
                    d_walk.push_back({cl, cr, h});

                    dbg("A", *it, qr);
                    assert(*it <= qr);
                    if (*it == qr) {
                        break;
                    }
                }
            }
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        dbg(ql, qr, h);
    }

    using S = pair<int, int>;

    S s_src {src, 0}, s_dest {dest, 0};
    vector<S> states {s_src, s_dest};
    for (auto& [ql, qr, h] : d_walk) {
        states.emplace_back(ql, h);
        states.emplace_back(qr, h);
    }

    sort(begin(states), end(states));
    states.erase(unique(begin(states), end(states)), states.end());

    map<int, vector<int>> buildings;
    for (auto& [x, y] : states) {
        buildings[x].push_back(y);
    }

    vector<tuple<S, S, long>> edges;

    for (auto& [x, ys] : buildings) {
        sort(begin(ys), end(ys));
        for (int i = 0; i + 1 < sz(ys); i++) {
            edges.emplace_back(S(x, ys[i]), S(x, ys[i + 1]), ys[i + 1] - ys[i]);
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        edges.emplace_back(S(ql, h), S(qr, h), qr - ql);
    }

    for (auto& [u, v, w] : edges) {
        dbg(u, v, w);
    }

    return dijkstra(edges, s_src, s_dest);
}

}  // namespace s1

ll min_distance(vector<int> arr_x,
                vector<int> arr_h,
                vector<int> walk_l,
                vector<int> walk_r,
                vector<int> walk_y,
                int src,
                int dest) {
    int n = sz(arr_x), m = sz(walk_l);

    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = {arr_x[i], arr_h[i]};
    }

    vector<array<int, 3>> walk(m);
    for (int i = 0; i < m; i++) {
        walk[i] = {walk_l[i], walk_r[i], walk_y[i]};
    }

    return s1::solve(arr, walk, src, dest);
}

Compilation message (stderr)

walk.cpp: In function 'int64_t s1::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:154:16: warning: unused structured binding declaration [-Wunused-variable]
  154 |     for (auto& [ql, qr, h] : d_walk) {
      |                ^~~~~~~~~~~
walk.cpp:188:16: warning: unused structured binding declaration [-Wunused-variable]
  188 |     for (auto& [u, v, w] : edges) {
      |                ^~~~~~~~~

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