제출 #1324048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324048		sh_qaxxorov_571	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	351 ms	23344 KiB

skyscraper

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

const int INF = 1e9;
const int MAXN = 30005;
const int SQRT = 175; // N ning kvadrat ildizi atrofida

int dist[MAXN][SQRT + 5];
vector<int> doges[MAXN];
int N, M;

struct State {
    int b, p, d;
    bool operator>(const State& other) const {
        return d > other.d;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    int start_b, target_b;
    
    for (int i = 0; i < M; i++) {
        int b, p;
        cin >> b >> p;
        if (i == 0) start_b = b;
        if (i == 1) target_b = b;
        doges[b].push_back(p);
    }

    // Masofalarni cheksizlik bilan to'ldirish
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= SQRT; j++) dist[i][j] = INF;
    }

    priority_queue<State, vector<State>, greater<State>> pq;
    
    // Boshlang'ich holat: binoda turganimizda p=0 deb hisoblaymiz
    dist[start_b][0] = 0;
    pq.push({start_b, 0, 0});

    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();

        int b = curr.b;
        int p = curr.p;
        int d = curr.d;

        if (d > dist[b][p]) continue;
        if (b == target_b) {
            cout << d << endl;
            return 0;
        }

        // Agar biz binoda bo'lsak (p == 0), shu binodagi barcha dogelarni ishga tushiramiz
        if (p == 0) {
            for (int np : doges[b]) {
                if (np > SQRT) {
                    // Katta qadamlar uchun oddiy sakrash
                    for (int i = 1; b + i * np < N; i++) {
                        if (d + i < dist[b + i * np][0]) {
                            dist[b + i * np][0] = d + i;
                            pq.push({b + i * np, 0, d + i});
                        }
                    }
                    for (int i = 1; b - i * np >= 0; i++) {
                        if (d + i < dist[b - i * np][0]) {
                            dist[b - i * np][0] = d + i;
                            pq.push({b - i * np, 0, d + i});
                        }
                    }
                } else {
                    // Kichik qadamlar uchun holatga o'tamiz
                    if (d < dist[b][np]) {
                        dist[b][np] = d;
                        pq.push({b, np, d});
                    }
                }
            }
        } else {
            // Kichik qadam p bilan sakrash
            // 1. O'ngga
            if (b + p < N && d + 1 < dist[b + p][p]) {
                dist[b + p][p] = d + 1;
                pq.push({b + p, p, d + 1});
            }
            // 2. Chapga
            if (b - p >= 0 && d + 1 < dist[b - p][p]) {
                dist[b - p][p] = d + 1;
                pq.push({b - p, p, d + 1});
            }
            // 3. Shu binoda to'xtash (xabarni uzatish)
            if (d < dist[b][0]) {
                dist[b][0] = d;
                pq.push({b, 0, d});
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43