oj.uz

Submission #761400

# Submission time Handle Problem Language Result Execution time Memory
761400 2023-06-19T15:20:59 Z MinaRagy06 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 259496 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#pragma GCC optimize("Ofast")

vector<int> intersect[100'005];
vector<pair<int, int>> 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({intersect[i][k + 1], idx[intersect[i][k + 1]].size() - 1});
            }
            if (k - 1 >= 0) {
                adj[intersect[i][k]].push_back({intersect[i][k - 1], idx[intersect[i][k - 1]].size() - 1});
            }
        }
        // assert(intersect[i].size() <= 10);
    }
    priority_queue<pair<ll, pair<int, int>>> pq;
    pq.push({0, {s, 0}});
    while (pq.size()) {
        ll d = -pq.top().first;
        int i = pq.top().second.first;
        int j = pq.top().second.second;
        pq.pop();
        if (d > dist[i][j]) continue;
        j = y[idx[i][j]];
        for (auto [nxt, nxth] : adj[i]) {
            ll newd = d + abs(x[nxt] - x[i]) + abs(j - y[idx[nxt][nxth]]);
            if (newd < dist[nxt][nxth]) {
                dist[nxt][nxth] = newd;
                pq.push({-newd, {nxt, nxth}});
            }
        }
    }
    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;
}

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:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (k + 1 < intersect[i].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     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 9760 KB Output is correct
3 Correct 5 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 6 ms 9780 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 7 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 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 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 1600 ms 55092 KB Output is correct
4 Correct 441 ms 54108 KB Output is correct
5 Correct 236 ms 50760 KB Output is correct
6 Correct 182 ms 47308 KB Output is correct
7 Correct 201 ms 50860 KB Output is correct
8 Correct 3119 ms 86604 KB Output is correct
9 Correct 275 ms 48996 KB Output is correct
10 Correct 774 ms 71728 KB Output is correct
11 Correct 206 ms 32028 KB Output is correct
12 Correct 114 ms 32824 KB Output is correct
13 Correct 578 ms 68732 KB Output is correct
14 Correct 133 ms 32620 KB Output is correct
15 Correct 147 ms 32844 KB Output is correct
16 Correct 582 ms 32508 KB Output is correct
17 Correct 132 ms 31572 KB Output is correct
18 Execution timed out 4067 ms 31576 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17080 KB Output is correct
2 Execution timed out 4085 ms 259496 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 17080 KB Output is correct
2 Execution timed out 4085 ms 259496 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 5 ms 9760 KB Output is correct
3 Correct 5 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 6 ms 9780 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 7 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 4 ms 9684 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 1600 ms 55092 KB Output is correct
21 Correct 441 ms 54108 KB Output is correct
22 Correct 236 ms 50760 KB Output is correct
23 Correct 182 ms 47308 KB Output is correct
24 Correct 201 ms 50860 KB Output is correct
25 Correct 3119 ms 86604 KB Output is correct
26 Correct 275 ms 48996 KB Output is correct
27 Correct 774 ms 71728 KB Output is correct
28 Correct 206 ms 32028 KB Output is correct
29 Correct 114 ms 32824 KB Output is correct
30 Correct 578 ms 68732 KB Output is correct
31 Correct 133 ms 32620 KB Output is correct
32 Correct 147 ms 32844 KB Output is correct
33 Correct 582 ms 32508 KB Output is correct
34 Correct 132 ms 31572 KB Output is correct
35 Execution timed out 4067 ms 31576 KB Time limit exceeded
36 Halted 0 ms 0 KB -