oj.uz

Submission #761420

# Submission time Handle Problem Language Result Execution time Memory
761420 2023-06-19T15:38:20 Z MinaRagy06 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 389600 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);
    }
    priority_queue<pair<ll, array<int, 3>>> pq;
    pq.push({0, {s, 0, 0}});
    int cnt = 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++;
        assert(cnt <= 1'000'000);
        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:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     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 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 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 6 ms 9812 KB Output is correct
9 Correct 5 ms 9788 KB Output is correct
10 Correct 5 ms 9740 KB Output is correct
11 Correct 5 ms 9696 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9760 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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 1696 ms 68820 KB Output is correct
4 Correct 529 ms 61120 KB Output is correct
5 Correct 213 ms 56656 KB Output is correct
6 Correct 195 ms 52116 KB Output is correct
7 Correct 266 ms 56632 KB Output is correct
8 Correct 3336 ms 113348 KB Output is correct
9 Correct 307 ms 55148 KB Output is correct
10 Runtime error 781 ms 167020 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 43 ms 17712 KB Output is correct
2 Execution timed out 4072 ms 389600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17712 KB Output is correct
2 Execution timed out 4072 ms 389600 KB Time limit exceeded
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 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 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 6 ms 9812 KB Output is correct
9 Correct 5 ms 9788 KB Output is correct
10 Correct 5 ms 9740 KB Output is correct
11 Correct 5 ms 9696 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9760 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 1696 ms 68820 KB Output is correct
21 Correct 529 ms 61120 KB Output is correct
22 Correct 213 ms 56656 KB Output is correct
23 Correct 195 ms 52116 KB Output is correct
24 Correct 266 ms 56632 KB Output is correct
25 Correct 3336 ms 113348 KB Output is correct
26 Correct 307 ms 55148 KB Output is correct
27 Runtime error 781 ms 167020 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -