oj.uz

Submission #610337

# Submission time Handle Problem Language Result Execution time Memory
610337 2022-07-28T06:46:06 Z KoD Sky Walking (IOI19_walk) C++17
0 / 100
 875 ms 79820 KB 
#include "walk.h"
#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<T>>;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int src, int dst) {
    const int N = (int)X.size();
    for (const int pivot : {src, dst}) {
        const int M = (int)Y.size();
        vector<pair<int, int>> left, right;
        for (int i = pivot; i >= 0; --i) {
            if (left.empty() or left.back().first < H[i]) {
                left.emplace_back(H[i], i);
            }
        }
        for (int i = pivot; i < N; ++i) {
            if (right.empty() or right.back().first < H[i]) {
                right.emplace_back(H[i], i);
            }
        }
        for (int i = 0; i < M; ++i) {
            if (L[i] < pivot and pivot < R[i]) {
                const int a = std::lower_bound(left.begin(), left.end(), pair(Y[i], 0))->second;
                const int b = std::lower_bound(right.begin(), right.end(), pair(Y[i], 0))->second;
                L.push_back(L[i]);
                R.push_back(a);
                Y.push_back(Y[i]);
                L.push_back(b);
                R.push_back(R[i]);
                Y.push_back(Y[i]);
                L[i] = a;
                R[i] = b;
            }
        }
    }
    vector<vector<pair<int, int>>> graph(N);
    const auto add_vertex = [&] {
        graph.emplace_back();
        return (int)graph.size() - 1;
    };
    const auto add_edge = [&](const int u, const int v, const int c) {
        graph[u].emplace_back(v, c);
        graph[v].emplace_back(u, c);
    };
    vector<vector<pair<int, int>>> vertices(N);
    for (int i = 0; i < N; ++i) {
        vertices[i].emplace_back(0, i);
    }
    const int M = (int)Y.size();
    vector<int> order(M);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](const int i, const int j) {
        return Y[i] > Y[j];
    });
    std::set<int> important;
    for (const int e : order) {
        if (L[e] == R[e]) {
            continue;
        }
        vertices[L[e]].emplace_back(Y[e], add_vertex());
        important.insert(L[e]);
        important.insert(R[e]);
        auto itr = important.upper_bound(L[e]);
        while (true) {
            const int a = *std::prev(itr);
            const int b = *itr;
            const int u = vertices[a].back().second;
            vertices[b].emplace_back(Y[e], add_vertex());
            const int v = vertices[b].back().second;
            add_edge(u, v, X[b] - X[a]);
            if (*itr == R[e]) {
                break;
            } else {
                itr = important.erase(itr);
            }
        }
    }
    std::set<int> remain;
    for (int i = 0; i < N; ++i) {
        remain.insert(i);
    }
    std::reverse(order.begin(), order.end());
    for (const int e : order) {
        if (L[e] == R[e]) {
            continue;
        }
        vector<int> list;
        list.push_back(L[e]);
        for (auto itr = remain.upper_bound(L[e]); itr != remain.end() and *itr < R[e]; itr = remain.erase(itr)) {
            if (Y[e] <= H[*itr]) {
                list.push_back(*itr);
            }
        }
        list.push_back(R[e]);
        const int n = (int)list.size();
        vector<int> id(n);
        for (int i = 0; i < n; ++i) {
            id[i] = add_vertex();
            vertices[list[i]].emplace_back(Y[e], id[i]);
        }
        for (int i = 0; i + 1 < n; ++i) {
            add_edge(id[i], id[i + 1], X[list[i + 1]] - X[list[i]]);
        }
    }
    for (auto& vec : vertices) {
        std::sort(vec.begin(), vec.end());
        const int n = (int)vec.size();
        for (int i = 0; i + 1 < n; ++i) {
            add_edge(vec[i].second, vec[i + 1].second, vec[i + 1].first - vec[i].first);
        }
    }
    vector<ll> dist(graph.size(), std::numeric_limits<ll>::max());
    min_heap<pair<ll, int>> heap;
    const auto push = [&](const int u, const ll d) {
        if (dist[u] > d) {
            dist[u] = d;
            heap.emplace(d, u);
        }
    };
    push(src, 0);
    while (!heap.empty()) {
        const auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) {
            continue;
        }
        for (const auto& [v, c] : graph[u]) {
            push(v, d + c);
        }
    }
    const ll ret = dist[dst];
    return ret == std::numeric_limits<ll>::max() ? -1 : ret;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 300 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 580 ms 58904 KB Output is correct
4 Incorrect 875 ms 79820 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 23152 KB Output is correct
2 Incorrect 643 ms 64540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 23152 KB Output is correct
2 Incorrect 643 ms 64540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 300 KB Output isn't correct
18 Halted 0 ms 0 KB -