Submission #1162168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162168		minhpk	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	15 ms	25416 KiB

skyscraper

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


struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        auto h1 = std::hash<int>()(p.first);
        auto h2 = std::hash<int>()(p.second);
        return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
    }
};

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

struct node {
    int val, pos, type;
};

unordered_map<pair<int, int>, int, PairHash> dist;


void dial() {

    int maxD = 2 * a;
    vector<vector<node>> buckets(maxD + 1);


    buckets[0].push_back({0, mark[0].first, mark[0].second});
    dist[{mark[0].first, mark[0].second}] = 0;


    for (int d = 0; d <= maxD; d++) {
        while (!buckets[d].empty()) {
            node cur = buckets[d].back();
            buckets[d].pop_back();

            if (dist[{cur.pos, cur.type}] < d) continue;


            if (cur.type == 0) {

                for (auto p : z[cur.pos]) {

                    int newPos = cur.pos + p;
                    if (newPos < a) {
                        pair<int,int> key = {newPos, p};
                        int nd = d + 1;
                        if (!dist.count(key) || dist[key] > nd) {
                            dist[key] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, p});
                            }
                        }
                    }

                    newPos = cur.pos - p;
                    if (newPos >= 0) {
                        pair<int,int> key = {newPos, p};
                        int nd = d + 1;
                        if (!dist.count(key) || dist[key] > nd) {
                            dist[key] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, p});
                            }
                        }
                    }
                }
            } else {

                pair<int,int> key0 = {cur.pos, 0};
                if (!dist.count(key0) || dist[key0] > d) {
                    dist[key0] = d;
                    buckets[d].push_back({d, cur.pos, 0});
                }

                if (cur.type > blocksize) {

                    int step = 1;
                    while (cur.pos + step * cur.type < a) {
                        int newPos = cur.pos + step * cur.type;
                        pair<int,int> key0 = {newPos, 0};
                        int nd = d + step;
                        if (!dist.count(key0) || dist[key0] > nd) {
                            dist[key0] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, 0});
                            }
                        }
                        step++;
                    }
                    step = 1;
                    while (cur.pos - step * cur.type >= 0) {
                        int newPos = cur.pos - step * cur.type;
                        pair<int,int> key0 = {newPos, 0};
                        int nd = d + step;
                        if (!dist.count(key0) || dist[key0] > nd) {
                            dist[key0] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, 0});
                            }
                        }
                        step++;
                    }
                } else {

                    int newPos = cur.pos + cur.type;
                    if (newPos < a) {
                        pair<int,int> key = {newPos, cur.type};
                        int nd = d + 1;
                        if (!dist.count(key) || dist[key] > nd) {
                            dist[key] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, cur.type});
                            }
                        }
                    }
                    newPos = cur.pos - cur.type;
                    if (newPos >= 0) {
                        pair<int,int> key = {newPos, cur.type};
                        int nd = d + 1;
                        if (!dist.count(key) || dist[key] > nd) {
                            dist[key] = nd;
                            if (nd <= maxD) {
                                buckets[nd].push_back({nd, newPos, cur.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;
    }


    dist.reserve(100000);

    dial();


    pair<int,int> finalKey = {mark[1].first, 0};
    if(dist.count(finalKey)){
        cout << dist[finalKey];
    } else {
        cout << -1;
    }
    return 0;
}

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