oj.uz

Submission #1037264

# Submission time Handle Problem Language Result Execution time Memory
1037264 2024-07-28T11:55:40 Z shmax Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 606664 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
using i32 = int;
#define int long long
#define all(x) x.begin(), x.end()
#define len(x) (int)(x.size())
#define inf 1000'000'000'000'000'000LL
#define bit(x, i) (((x) >> i) & 1)

template<typename T>
using vec = vector<T>;


int min_distance(std::vector<i32> x, std::vector<i32> h, std::vector<i32> L,
                 std::vector<i32> R, std::vector<i32> Y, i32 s, i32 e) {
    int n = len(x);
    set<int> exist;
    for (int i = 0; i < n; i++)
        exist.insert(i);
    struct line {
        int l, r, h;
    };
    vec<line> lines;
    for (int i = 0; i < len(L); i++) {
        lines.push_back({L[i], R[i], Y[i]});
    }
    sort(all(lines), [&](line a, line b) {
        return a.h < b.h;
    });
    vec<int> buildings(n);
    iota(all(buildings), 0);
    sort(all(buildings), [&](int i, int j) {
        return h[i] < h[j];
    });
    int ptr = 0;
    map<pair<int, int>, int> ids;
    int cur_id = 0;
    vec<vec<pair<int, int>>> g;
    auto create = [&](pair<int, int> a) {
        if (!ids.count(a)) {
            ids[a] = cur_id++;
            g.emplace_back();
        }
    };

    auto add_edge = [&](pair<int, int> f1, pair<int, int> f2) {
        int v = ids[f1];
        int u = ids[f2];
        g[v].push_back({u, abs(f1.first - f2.first) + abs(f1.second - f2.second)});
        g[u].push_back({v, abs(f1.first - f2.first) + abs(f1.second - f2.second)});
    };
    vec<vec<pair<int, int>>> points_build(n);
    for (auto [l, r, y]: lines) {
        while (ptr < n and h[buildings[ptr]] < y) {
            exist.erase(buildings[ptr]);
            ptr++;
        }
        vec<pair<int, int>> points;
        auto ptr = exist.lower_bound(l);
        while (ptr != exist.end() and *ptr <= r) {
            create({x[*ptr], y});
            points.push_back({x[*ptr], y});
            points_build[*ptr].push_back({x[*ptr], y});
            ptr++;
        }
        for (int i = 1; i < len(points); i++) {
            add_edge(points[i - 1], points[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        create({x[i], 0});
        points_build[i].push_back({x[i], 0});
        sort(all(points_build[i]));
        for (int j = 1; j < len(points_build[i]); j++) {
            add_edge(points_build[i][j - 1], points_build[i][j]);
        }
    }

    int m = len(ids);
    vec<int> dist(m, inf);
    dist[ids[{x[s], 0}]] = 0;
    priority_queue<pair<int, int>, vec<pair<int, int>>, greater<>> pq;
    pq.push({0, ids[{x[s], 0}]});
    while (!pq.empty()) {
        auto [dst, v] = pq.top();
        pq.pop();
        if (dst > dist[v]) continue;
        for (auto [u, w]: g[v]) {
            if (dist[u] > dst + w) {
                dist[u] = dst + w;
                pq.push({dist[u], u});
            }
        }
    }
    if (dist[ids[{x[e], 0}]] == inf) dist[ids[{x[e], 0}]] = -1;
    return dist[ids[{x[e], 0}]];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1189 ms 159952 KB Output is correct
4 Correct 1268 ms 175280 KB Output is correct
5 Correct 831 ms 151676 KB Output is correct
6 Correct 789 ms 134316 KB Output is correct
7 Correct 798 ms 152748 KB Output is correct
8 Correct 1368 ms 197812 KB Output is correct
9 Correct 957 ms 150008 KB Output is correct
10 Correct 1745 ms 235176 KB Output is correct
11 Correct 638 ms 91060 KB Output is correct
12 Correct 419 ms 69556 KB Output is correct
13 Correct 1478 ms 209064 KB Output is correct
14 Correct 313 ms 64808 KB Output is correct
15 Correct 336 ms 65344 KB Output is correct
16 Correct 336 ms 66408 KB Output is correct
17 Correct 376 ms 65376 KB Output is correct
18 Correct 266 ms 71020 KB Output is correct
19 Correct 9 ms 3420 KB Output is correct
20 Correct 116 ms 31936 KB Output is correct
21 Correct 340 ms 64956 KB Output is correct
22 Correct 391 ms 64652 KB Output is correct
23 Correct 298 ms 81840 KB Output is correct
24 Correct 336 ms 66228 KB Output is correct
25 Correct 391 ms 65204 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 23492 KB Output is correct
2 Execution timed out 4072 ms 606664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 23492 KB Output is correct
2 Execution timed out 4072 ms 606664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1189 ms 159952 KB Output is correct
21 Correct 1268 ms 175280 KB Output is correct
22 Correct 831 ms 151676 KB Output is correct
23 Correct 789 ms 134316 KB Output is correct
24 Correct 798 ms 152748 KB Output is correct
25 Correct 1368 ms 197812 KB Output is correct
26 Correct 957 ms 150008 KB Output is correct
27 Correct 1745 ms 235176 KB Output is correct
28 Correct 638 ms 91060 KB Output is correct
29 Correct 419 ms 69556 KB Output is correct
30 Correct 1478 ms 209064 KB Output is correct
31 Correct 313 ms 64808 KB Output is correct
32 Correct 336 ms 65344 KB Output is correct
33 Correct 336 ms 66408 KB Output is correct
34 Correct 376 ms 65376 KB Output is correct
35 Correct 266 ms 71020 KB Output is correct
36 Correct 9 ms 3420 KB Output is correct
37 Correct 116 ms 31936 KB Output is correct
38 Correct 340 ms 64956 KB Output is correct
39 Correct 391 ms 64652 KB Output is correct
40 Correct 298 ms 81840 KB Output is correct
41 Correct 336 ms 66228 KB Output is correct
42 Correct 391 ms 65204 KB Output is correct
43 Correct 105 ms 23492 KB Output is correct
44 Execution timed out 4072 ms 606664 KB Time limit exceeded
45 Halted 0 ms 0 KB -