oj.uz

Submission #792280

# Submission time Handle Problem Language Result Execution time Memory
792280 2023-07-24T23:36:03 Z skittles1412 Sky Walking (IOI19_walk) C++17
24 / 100
 3110 ms 1048576 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template <typename T>
struct Comp {
    map<T, int> mp;

    int operator()(const T& t) {
        auto [it, inserted] = mp.emplace(t, -1);
        if (inserted) {
            it->second = sz(mp) - 1;
        }
        return it->second;
    }
};

template <typename S>
long dijkstra(const vector<tuple<S, S, long>>& edges, S src, S dest) {
    dbg("A");
    int n = 2 * sz(edges) + 10;

    Comp<S> comp;
    vector<pair<int, long>> graph[n];

    for (auto& [u, v, w] : edges) {
        int cu = comp(u), cv = comp(v);
        graph[cu].emplace_back(cv, w);
        graph[cv].emplace_back(cu, w);
    }

    long dist[n];
    memset(dist, 0x3f, sizeof(dist));

    min_pq<pair<long, int>> pq;
    auto push = [&](int u, long d) -> void {
        if (d >= dist[u]) {
            return;
        }
        dist[u] = d;
        pq.emplace(d, u);
    };

    int c_src = comp(src), c_dest = comp(dest);

    push(c_src, 0);

    while (sz(pq)) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == c_dest) {
            return d;
        }
        if (d != dist[u]) {
            continue;
        }

        for (auto& [v, w] : graph[u]) {
            push(v, d + w);
        }
    }

    return -1;
}

namespace s1 {

long solve(vector<pair<int, int>> arr,
           vector<array<int, 3>> walk,
           int src,
           int dest) {
    src = arr[src].first;
    dest = arr[dest].first;

    map<int, vector<pair<int, int>>> evts;
    for (auto& [x, h] : arr) {
        evts[-h].emplace_back(x, -1);
    }
    for (auto& [ql, qr, h] : walk) {
        ql = arr[ql].first;
        qr = arr[qr].first;
        evts[-h].emplace_back(ql, qr);
    }

    vector<array<int, 3>> d_walk;
    {
        set<int> pos;
        for (auto& [nh, ev] : evts) {
            int h = -nh;

            for (auto& [x, ty] : ev) {
                if (ty == -1) {
                    dbg(h, x);
                    pos.insert(x);
                }
            }

            for (auto& [ql, qr] : ev) {
                if (qr == -1) {
                    continue;
                }
                dbg(h, ql, qr);

                auto it = pos.lower_bound(ql);
                while (true) {
                    int cl = *it;
                    ++it;
                    int cr = *it;
                    d_walk.push_back({cl, cr, h});

                    dbg("A", *it, qr);
                    assert(*it <= qr);
                    if (*it == qr) {
                        break;
                    }
                }
            }
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        dbg(ql, qr, h);
    }

    using S = pair<int, int>;

    S s_src {src, 0}, s_dest {dest, 0};
    vector<S> states {s_src, s_dest};
    for (auto& [ql, qr, h] : d_walk) {
        states.emplace_back(ql, h);
        states.emplace_back(qr, h);
    }

    sort(begin(states), end(states));
    states.erase(unique(begin(states), end(states)), states.end());

    map<int, vector<int>> buildings;
    for (auto& [x, y] : states) {
        buildings[x].push_back(y);
    }

    vector<tuple<S, S, long>> edges;

    for (auto& [x, ys] : buildings) {
        sort(begin(ys), end(ys));
        for (int i = 0; i + 1 < sz(ys); i++) {
            edges.emplace_back(S(x, ys[i]), S(x, ys[i + 1]), ys[i + 1] - ys[i]);
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        edges.emplace_back(S(ql, h), S(qr, h), qr - ql);
    }

    for (auto& [u, v, w] : edges) {
        dbg(u, v, w);
    }

    return dijkstra(edges, s_src, s_dest);
}

}  // namespace s1

ll min_distance(vector<int> arr_x,
                vector<int> arr_h,
                vector<int> walk_l,
                vector<int> walk_r,
                vector<int> walk_y,
                int src,
                int dest) {
    int n = sz(arr_x), m = sz(walk_l);

    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = {arr_x[i], arr_h[i]};
    }

    vector<array<int, 3>> walk(m);
    for (int i = 0; i < m; i++) {
        walk[i] = {walk_l[i], walk_r[i], walk_y[i]};
    }

    return s1::solve(arr, walk, src, dest);
}

Compilation message

walk.cpp: In function 'int64_t s1::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:154:16: warning: unused structured binding declaration [-Wunused-variable]
  154 |     for (auto& [ql, qr, h] : d_walk) {
      |                ^~~~~~~~~~~
walk.cpp:188:16: warning: unused structured binding declaration [-Wunused-variable]
  188 |     for (auto& [u, v, w] : edges) {
      |                ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1122 ms 282656 KB Output is correct
4 Correct 1255 ms 290232 KB Output is correct
5 Correct 855 ms 249472 KB Output is correct
6 Correct 797 ms 216332 KB Output is correct
7 Correct 945 ms 249592 KB Output is correct
8 Correct 1569 ms 361356 KB Output is correct
9 Correct 1130 ms 248632 KB Output is correct
10 Correct 1918 ms 409680 KB Output is correct
11 Correct 660 ms 145872 KB Output is correct
12 Correct 523 ms 88476 KB Output is correct
13 Correct 1579 ms 357268 KB Output is correct
14 Correct 326 ms 79888 KB Output is correct
15 Correct 308 ms 70964 KB Output is correct
16 Correct 298 ms 73044 KB Output is correct
17 Correct 291 ms 70328 KB Output is correct
18 Correct 276 ms 93580 KB Output is correct
19 Correct 9 ms 3924 KB Output is correct
20 Correct 104 ms 37304 KB Output is correct
21 Correct 334 ms 67888 KB Output is correct
22 Correct 298 ms 67996 KB Output is correct
23 Correct 359 ms 91492 KB Output is correct
24 Correct 292 ms 69924 KB Output is correct
25 Correct 292 ms 69432 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 27412 KB Output is correct
2 Runtime error 3110 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 27412 KB Output is correct
2 Runtime error 3110 ms 1048576 KB Execution killed with signal 9
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 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1122 ms 282656 KB Output is correct
21 Correct 1255 ms 290232 KB Output is correct
22 Correct 855 ms 249472 KB Output is correct
23 Correct 797 ms 216332 KB Output is correct
24 Correct 945 ms 249592 KB Output is correct
25 Correct 1569 ms 361356 KB Output is correct
26 Correct 1130 ms 248632 KB Output is correct
27 Correct 1918 ms 409680 KB Output is correct
28 Correct 660 ms 145872 KB Output is correct
29 Correct 523 ms 88476 KB Output is correct
30 Correct 1579 ms 357268 KB Output is correct
31 Correct 326 ms 79888 KB Output is correct
32 Correct 308 ms 70964 KB Output is correct
33 Correct 298 ms 73044 KB Output is correct
34 Correct 291 ms 70328 KB Output is correct
35 Correct 276 ms 93580 KB Output is correct
36 Correct 9 ms 3924 KB Output is correct
37 Correct 104 ms 37304 KB Output is correct
38 Correct 334 ms 67888 KB Output is correct
39 Correct 298 ms 67996 KB Output is correct
40 Correct 359 ms 91492 KB Output is correct
41 Correct 292 ms 69924 KB Output is correct
42 Correct 292 ms 69432 KB Output is correct
43 Correct 89 ms 27412 KB Output is correct
44 Runtime error 3110 ms 1048576 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -