oj.uz

답안 #424011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424011 2021-06-11T15:20:07 Z yuto1115 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 660948 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++]);
            }
            int cnt = 0;
            auto now = st.lower_bound(l[i]);
            while (now != st.end() and *now <= r[i]) {
                pos.eb(*now, y[i]);
                now++;
            }
            assert(cnt <= 10);
        }
    }
    sort(all(pos));
    pos.erase(unique(all(pos)), pos.end());
    int sz = pos.size();
    map<P, int> id;
    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++;
            }
        }
    }
    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
10.0 / 10.0

# 결과 실행 시간 메모리 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 Correct 7 ms 428 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 6 ms 292 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 3 ms 204 KB Output is correct
10 Correct 9 ms 332 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 288 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 204 KB Output is correct
17 Correct 12 ms 448 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 4070 ms 118604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 728 ms 13256 KB Output is correct
2 Execution timed out 4128 ms 660948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 728 ms 13256 KB Output is correct
2 Execution timed out 4128 ms 660948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 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 Correct 7 ms 428 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 6 ms 292 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 3 ms 204 KB Output is correct
10 Correct 9 ms 332 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 288 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 204 KB Output is correct
17 Correct 12 ms 448 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Execution timed out 4070 ms 118604 KB Time limit exceeded
21 Halted 0 ms 0 KB -