제출 #760533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760533		sheldon	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	69 ms	124976 KiB

skyscraper

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43