Submission #1162189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162189		minhpk	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	95352 KiB

skyscraper

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

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

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

int base;
inline long long encode(int pos, int type) {
    return (long long) pos * base + type;
}


unordered_map<long long, int> dist;

void dijkstra() {
    priority_queue<node, vector<node>, greater<node>> q;
    long long key0 = encode(mark[0].first, mark[0].second);
    dist[key0] = 0;
    q.push({0, mark[0].first, mark[0].second});

    
    auto relax = [&](int nd, int newPos, int newType) {
        long long key = encode(newPos, newType);
        auto it = dist.find(key);
        if (it == dist.end() || it->second > nd) {
            dist[key] = nd;
            q.push({nd, newPos, newType});
        }
    };

    while (!q.empty()) {
        node cur = q.top();
        q.pop();
        int d = cur.val, pos = cur.pos, type = cur.type;
        long long curKey = encode(pos, type);
        if (dist[curKey] < d) continue;

        if (type == 0) {
            
            for (int p : z[pos]) {
                int newPos = pos + p;
                if (newPos < a)
                    relax(d + 1, newPos, p);
                newPos = pos - p;
                if (newPos >= 0)
                    relax(d + 1, newPos, p);
            }
        } else {
           
            relax(d, pos, 0);

            if (type > blocksize) {
               
                int step = 1;
                while (pos + step * type < a) {
                    relax(d + step, pos + step * type, 0);
                    step++;
                }
                step = 1;
                while (pos - step * type >= 0) {
                    relax(d + step, pos - step * type, 0);
                    step++;
                }
            } else {
                int newPos = pos + type;
                if (newPos < a)
                    relax(d + 1, newPos, type);
                newPos = pos - type;
                if (newPos >= 0)
                    relax(d + 1, newPos, type);
            }
        }
    }
}

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

    cin >> a >> b;
    blocksize = sqrt(a);
    base = a + 1;

    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;
    }

    
    dist.reserve(100000);

    dijkstra();

    long long finalKey = encode(mark[1].first, 0);
    if (dist.find(finalKey) != dist.end())
        cout << dist[finalKey];
    else
        cout << -1;

    return 0;
}

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