oj.uz

Submission #760534

# Submission time Handle Problem Language Result Execution time Memory
760534 2023-06-17T18:05:32 Z sheldon Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 68 ms 124972 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 3e4 + 5;

vector<pair<int, int>> doges[nax];
const int B = 175;

vector<array<int, 3>> edges[nax][B];
bool has[nax][B];
int ans[nax][B];

void solve () {
        int n, m;
        cin >> n >> m;
        int start, finish;
        for (int i = 0; i < m; ++i) {
            int b, p;
            cin >> b >> p;
            if (i == 0) start = b;
            if (i == 1) finish = b;
            if (p < B)  {
                has[b][p] = 1;
            } else {
                for (int j = b + p; j < n; j += p) {
                    edges[b][0].push_back({j, 0,(j - b) / p});
                }
                for (int j = b - p; j >= 0; j -= p) {
                    edges[b][0].push_back({j, 0, (b - j) / p});
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            ans[i][0] = 1e9;
            for (int j = 1; j < B; ++j) {
                if (has[i][j]) {
                    edges[i][0].push_back({i, j, 0});
                }
                edges[i][j].push_back({i, 0, 0});
                ans[i][j] = 1e9;
            }

        }
        priority_queue<array<int, 3>> pq;
        pq.push({0, start, 0});
        ans[start][0] = 0;
        int answer = -1;
        while (!pq.empty()) {
            array<int, 3> a = pq.top();
            pq.pop();
            int dist = a[0], u = a[1], p = a[2];
            //cout << dist << ' ' << u << ' ' << p << '\n';
            if (u == finish) {
                answer = dist;
                break;
            }
            if (ans[u][p] != dist) continue;
            for (array<int, 3> v : edges[u][p]) {
                if (ans[v[0]][v[1]] > dist + v[2]) {
                    pq.push({ans[v[0]][v[1]] = dist + v[2], v[0], v[1]});
                }
            }
            if (p != 0 && u + p < n && ans[u + p][p] > dist + 1) {
                pq.push({ans[u + p][p] = dist + 1, u + p, p});
            }
            if (p != 0 && u - p >= 0 && ans[u - p][p] > dist + 1) {
                pq.push({ans[u - p][p] = dist + 1, u - p, p});
            }
        }
        cout << answer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:54:13: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |             if (u == finish) {
      |             ^~
skyscraper.cpp:47:23: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |         ans[start][0] = 0;
      |         ~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 124256 KB Output is correct
2 Correct 56 ms 124288 KB Output is correct
3 Correct 55 ms 124236 KB Output is correct
4 Correct 54 ms 124280 KB Output is correct
5 Correct 54 ms 124332 KB Output is correct
6 Correct 58 ms 124364 KB Output is correct
7 Correct 55 ms 124380 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 124252 KB Output is correct
2 Correct 57 ms 124264 KB Output is correct
3 Correct 57 ms 124272 KB Output is correct
4 Correct 60 ms 124364 KB Output is correct
5 Correct 57 ms 124392 KB Output is correct
6 Correct 68 ms 124512 KB Output is correct
7 Correct 62 ms 124316 KB Output is correct
8 Correct 56 ms 124540 KB Output is correct
9 Correct 57 ms 124620 KB Output is correct
10 Incorrect 57 ms 124948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 124236 KB Output is correct
2 Correct 59 ms 124400 KB Output is correct
3 Correct 57 ms 124244 KB Output is correct
4 Correct 57 ms 124276 KB Output is correct
5 Correct 65 ms 124364 KB Output is correct
6 Correct 56 ms 124328 KB Output is correct
7 Correct 59 ms 124384 KB Output is correct
8 Correct 57 ms 124620 KB Output is correct
9 Correct 68 ms 124620 KB Output is correct
10 Incorrect 58 ms 124972 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 124336 KB Output is correct
2 Correct 56 ms 124292 KB Output is correct
3 Correct 57 ms 124352 KB Output is correct
4 Correct 56 ms 124336 KB Output is correct
5 Correct 57 ms 124280 KB Output is correct
6 Correct 57 ms 124284 KB Output is correct
7 Correct 62 ms 124332 KB Output is correct
8 Correct 59 ms 124556 KB Output is correct
9 Correct 59 ms 124616 KB Output is correct
10 Incorrect 59 ms 124940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 124372 KB Output is correct
2 Correct 59 ms 124336 KB Output is correct
3 Correct 59 ms 124352 KB Output is correct
4 Correct 59 ms 124256 KB Output is correct
5 Correct 58 ms 124364 KB Output is correct
6 Correct 58 ms 124292 KB Output is correct
7 Correct 58 ms 124348 KB Output is correct
8 Correct 58 ms 124556 KB Output is correct
9 Correct 64 ms 124636 KB Output is correct
10 Incorrect 59 ms 124944 KB Output isn't correct
11 Halted 0 ms 0 KB -