oj.uz

Submission #423992

# Submission time Handle Problem Language Result Execution time Memory
423992 2021-06-11T15:05:34 Z yuto1115 Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 663556 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Runtime error 2 ms 640 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 4041 ms 120552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 13752 KB Output is correct
2 Execution timed out 4091 ms 663556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 13752 KB Output is correct
2 Execution timed out 4091 ms 663556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Runtime error 2 ms 640 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -