Submission #1162206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162206		minhpk	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	420 ms	51904 KiB

skyscraper

#include "bits/stdc++.h"
using namespace std;

const int MAX_POS = 300005;
const int MAX_TYPE = 180;
const long long INF = 1e18;

int a, b;
vector<int> z[MAX_POS];
int blocksize;
pair<int, int> mark[30005];

struct node {
    int val, pos, type;
    bool operator>(const node &other) const {
        return val > other.val;
    }
};

static long long dp[MAX_POS][MAX_TYPE];

void dijkstra() {
    for (int i = 0; i < a; i++) {
        for (int t = 0; t < MAX_TYPE; t++) {
            dp[i][t] = INF;
        }
    }
    int startPos = mark[0].first, startType = mark[0].second;
    dp[startPos][startType] = 0;
    priority_queue<node, vector<node>, greater<node>> pq;
    pq.push({0, startPos, startType});
    while (!pq.empty()) {
        node cur = pq.top();
        pq.pop();
        int d = cur.val, pos = cur.pos, type = cur.type;
        if (dp[pos][type] < d) continue;
        if (type == 0) {
            for (int p : z[pos]) {
                if (p <= blocksize) {
                    int newPos = pos + p;
                    if (newPos < a && p < MAX_TYPE) {
                        if (dp[newPos][p] > d + 1) {
                            dp[newPos][p] = d + 1;
                            pq.push({d + 1, newPos, p});
                        }
                    }
                    newPos = pos - p;
                    if (newPos >= 0 && p < MAX_TYPE) {
                        if (dp[newPos][p] > d + 1) {
                            dp[newPos][p] = d + 1;
                            pq.push({d + 1, newPos, p});
                        }
                    }
                } else {
                    for (int step = 1; pos + step * p < a; step++) {
                        int newPos = pos + step * p;
                        if (dp[newPos][0] > d + step) {
                            dp[newPos][0] = d + step;
                            pq.push({d + step, newPos, 0});
                        }
                    }
                    for (int step = 1; pos - step * p >= 0; step++) {
                        int newPos = pos - step * p;
                        if (dp[newPos][0] > d + step) {
                            dp[newPos][0] = d + step;
                            pq.push({d + step, newPos, 0});
                        }
                    }
                }
            }
        } else {
            if (dp[pos][0] > d) {
                dp[pos][0] = d;
                pq.push({d, pos, 0});
            }
            if (type > blocksize) {
                for (int step = 1; pos + step * type < a; step++) {
                    int newPos = pos + step * type;
                    if (dp[newPos][0] > d + step) {
                        dp[newPos][0] = d + step;
                        pq.push({d + step, newPos, 0});
                    }
                }
                for (int step = 1; pos - step * type >= 0; step++) {
                    int newPos = pos - step * type;
                    if (dp[newPos][0] > d + step) {
                        dp[newPos][0] = d + step;
                        pq.push({d + step, newPos, 0});
                    }
                }
            } else {
                int newPos = pos + type;
                if (newPos < a && type < MAX_TYPE) {
                    if (dp[newPos][type] > d + 1) {
                        dp[newPos][type] = d + 1;
                        pq.push({d + 1, newPos, type});
                    }
                }
                newPos = pos - type;
                if (newPos >= 0 && type < MAX_TYPE) {
                    if (dp[newPos][type] > d + 1) {
                        dp[newPos][type] = d + 1;
                        pq.push({d + 1, newPos, type});
                    }
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;
    blocksize = sqrt(a);
    for (int i = 0; i < b; i++){
        int x, y;
        cin >> x >> y;
        z[x].push_back(y);
        mark[i] = {x, y};
    }
    if(b == 0){
        cout << -1;
        return 0;
    }
    dijkstra();
    int finalPos = mark[1].first;
    if(dp[finalPos][0] < INF)
        cout << dp[finalPos][0];
    else
        cout << -1;
    return 0;
}

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