Submission #1162190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162190		minhpk	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1098 ms	95136 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 initKey = encode(mark[0].first, mark[0].second);
    dist[initKey] = 0;
    q.push({0, mark[0].first, mark[0].second});
    
    // Lambda relax() giúp cập nhật trạng thái mới nếu tìm được khoảng cách nhỏ hơn
    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) {
            // Với trạng thái type==0, duyệt qua tất cả các bước chuyển có giá trị p từ z[pos]
            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 {
            // Luôn chuyển về trạng thái (pos, 0) với chi phí không tăng
            relax(d, pos, 0);
            
            if (type > blocksize) {
                // Dùng for-loop thay vì while-loop cho hai hướng di chuyển
                for (int step = 1; pos + step * type < a; ++step)
                    relax(d + step, pos + step * type, 0);
                for (int step = 1; pos - step * type >= 0; ++step)
                    relax(d + step, pos - step * type, 0);
            } 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