제출 #422967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422967		yuto1115	Sky Walking (IOI19_walk)	C++17	0 / 100	81 ms	9884 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]; });
    rep(i, m) {
        pos.eb(l[i], y[i]);
        pos.eb(r[i], y[i]);
    }
    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);
        }
    rep(i, m) {
        int a = id[{l[i], y[i]}];
        int b = id[{l[i], y[i]}];
        G[a].eb(b, x[r[i]] - x[l[i]]);
        G[b].eb(a, x[r[i]] - x[l[i]]);
    }
    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