oj.uz

Submission #761422

# Submission time Handle Problem Language Result Execution time Memory
761422 2023-06-19T15:39:41 Z MinaRagy06 Sky Walking (IOI19_walk) C++17
10 / 100
 3259 ms 588952 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> intersect[100'005];
vector<array<int, 3>> adj[100'005];
vector<ll> dist[100'005];
vector<int> idx[100'005];
int sparse[17][200'005];
const ll INF = 1e18;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    int n = x.size(), m = l.size();
    for (int i = 0; i < n; i++) {
        sparse[0][i] = h[i];
    }
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
        }
    }
    y.push_back(0);
    idx[s].push_back(m);
    dist[s].push_back(INF);
    for (int i = 0; i < m; i++) {
        int j = l[i];
        while (j <= r[i]) {
            if (y[i] <= h[j]) {
                intersect[i].push_back(j);
                j++;
                continue;
            }
            int mx = 0;
            for (int k = 16; k >= 0; k--) {
                if (y[i] > max(mx, sparse[k][j])) {
                    mx = max(mx, sparse[k][j]);
                    j += (1 << k);
                }
            }
            if (j <= r[i]) {
                intersect[i].push_back(j);
                j++;
            }
        }
        for (int k = 0; k < intersect[i].size(); k++) {
            dist[intersect[i][k]].push_back(INF);
            idx[intersect[i][k]].push_back(i);
        }
        for (int k = 0; k < intersect[i].size(); k++) {
            if (k + 1 < intersect[i].size()) {
                adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k + 1], idx[intersect[i][k + 1]].size() - 1, y[i]});
            }
            if (k - 1 >= 0) {
                adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k - 1], idx[intersect[i][k - 1]].size() - 1, y[i]});
            }
        }
        // assert(intersect[i].size() <= 10);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += idx[i].size();
    }
    assert(cnt <= 1'000'000);
    priority_queue<pair<ll, array<int, 3>>> pq;
    pq.push({0, {s, 0, 0}});
    while (pq.size()) {
        ll d = -pq.top().first;
        int i = pq.top().second[0];
        int j = pq.top().second[1];
        int cury = pq.top().second[2];
        pq.pop();
        if (d > dist[i][j]) continue;
        cnt++;
        for (auto [nxt, nxth, w] : adj[i]) {
            ll newd = d + abs(x[nxt] - x[i]) + abs(cury - w);
            if (newd < dist[nxt][nxth]) {
                dist[nxt][nxth] = newd;
                pq.push({-newd, {nxt, nxth, w}});
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < dist[g].size(); i++) {
        ans = min(ans, dist[g][i] + y[idx[g][i]]);
    }
    // for (auto i : dist[g]) {
    //     ans = min(ans, i.first + i.second);
    // }
    if (ans >= INF) return -1;
    return ans;
}
// int main() {
//     ios_base::sync_with_stdio(0), cin.tie(0);
//     int N, M;
//     cin >> N >> M;
//     vector<int> X(N), H(N);
//     for (int i = 0; i < N; i++) {
//         cin >> X[i] >> H[i];
//     }
//     vector<int> L(M), R(M), Y(M);
//     for (int i = 0; i < M; i++) {
//         cin >> L[i] >> R[i] >> Y[i];
//     }
//     int S, G;
//     cin >> S >> G;
//     cout << min_distance(X, H, L, R, Y, S, G) << '\n';
//     return 0;
// }

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             if (k + 1 < intersect[i].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:50:118: warning: narrowing conversion of '(idx[intersect[i].std::vector<int>::operator[](((std::vector<int>::size_type)(k + 1)))].std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   50 |                 adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k + 1], idx[intersect[i][k + 1]].size() - 1, y[i]});
      |                                                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
walk.cpp:53:118: warning: narrowing conversion of '(idx[intersect[i].std::vector<int>::operator[](((std::vector<int>::size_type)(k - 1)))].std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   53 |                 adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k - 1], idx[intersect[i][k - 1]].size() - 1, y[i]});
      |                                                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
walk.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < dist[g].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 1643 ms 68780 KB Output is correct
4 Correct 489 ms 61068 KB Output is correct
5 Correct 208 ms 56760 KB Output is correct
6 Correct 211 ms 52116 KB Output is correct
7 Correct 221 ms 56736 KB Output is correct
8 Correct 3259 ms 113284 KB Output is correct
9 Correct 315 ms 54980 KB Output is correct
10 Runtime error 440 ms 165480 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17800 KB Output is correct
2 Runtime error 646 ms 588952 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17800 KB Output is correct
2 Runtime error 646 ms 588952 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 4 ms 9812 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9756 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 4 ms 9684 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 5 ms 9728 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 1643 ms 68780 KB Output is correct
21 Correct 489 ms 61068 KB Output is correct
22 Correct 208 ms 56760 KB Output is correct
23 Correct 211 ms 52116 KB Output is correct
24 Correct 221 ms 56736 KB Output is correct
25 Correct 3259 ms 113284 KB Output is correct
26 Correct 315 ms 54980 KB Output is correct
27 Runtime error 440 ms 165480 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -