제출 #423992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423992		yuto1115	Sky Walking (IOI19_walk)	C++17	0 / 100	4091 ms	663556 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n = x.size();
    int m = l.size();
    vp pos;
    pos.eb(s, 0);
    pos.eb(g, 0);
    vi ob(n);
    iota(all(ob), 0);
    sort(all(ob), [&](int i, int j) { return h[i] < h[j]; });
    vi oe(m);
    iota(all(oe), 0);
    sort(all(oe), [&](int i, int j) { return y[i] < y[j]; });
    {
        set<int> st;
        rep(i, n) st.insert(i);
        int it = 0;
        for (int i : oe) {
            while (it < n and h[ob[it]] < y[i]) {
                st.erase(ob[it++]);
            }
            auto now = st.lower_bound(l[i]);
            while (now != st.end() and *now <= r[i]) {
                pos.eb(*now, y[i]);
                now++;
            }
        }
    }
    sort(all(pos));
    pos.erase(unique(all(pos)), pos.end());
    map<P, int> id;
    int sz = pos.size();
    rep(i, sz) id[pos[i]] = i;
    vvp G(sz);
    rep(i, sz - 1) if (pos[i].first == pos[i + 1].first) {
            G[i].eb(i + 1, pos[i + 1].second - pos[i].second);
            G[i + 1].eb(i, pos[i + 1].second - pos[i].second);
        }
    {
        set<int> st;
        rep(i, n) st.insert(i);
        int it = 0;
        for (int i : oe) {
            while (it < n and h[ob[it]] < y[i]) {
                st.erase(ob[it++]);
            }
            auto now = st.lower_bound(l[i]);
            int pre = -1;
            while (now != st.end() and *now <= r[i]) {
                int nx = id[{*now, y[i]}];
                if (pre >= 0) {
                    assert(pos[nx].first >= pos[pre].first);
                    G[pre].eb(nx, x[pos[nx].first] - x[pos[pre].first]);
                    G[nx].eb(pre, x[pos[nx].first] - x[pos[pre].first]);
                }
                pre = nx;
                now++;
            }
        }
    }
    assert(sz <= 2 + 10 * m);
    vl dist(sz, linf);
    using lp = pair<ll, int>;
    priority_queue<lp, vector<lp>, greater<lp>> pq;
    dist[id[{s, 0}]] = 0;
    pq.emplace(0, id[{s, 0}]);
    while (!pq.empty()) {
        auto[d, u] = pq.top();
        pq.pop();
        if (dist[u] < d) continue;
        cerr << d << ' ' << pos[u].first << ' ' << pos[u].second << endl;
        for (auto[v, len] : G[u]) {
            if (chmin(dist[v], d + len)) pq.emplace(d + len, v);
        }
    }
    ll ans = dist[id[{g, 0}]];
    return (ans == linf ? -1 : ans);
}

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