Submission #316930

#	Time	Username	Problem	Language	Result	Execution time	Memory
316930		uno	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	930 ms	7284 KiB

skyscraper

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

using namespace std;

int N, M;
vector<set<int>> jump;
vector<int> discovered;
vector<unordered_map<int,int>> adjList;


int firstDogeLoc = 0, firstJump = 0;
int secondDogeLoc= 0, secondJump = 0;
void input()
{
    cin >> N >> M;
    jump = vector<set<int>>(N,set<int>());

    cin >> firstDogeLoc >> firstJump;
    jump[firstDogeLoc].emplace(firstJump);

    cin >> secondDogeLoc >> secondJump;
    jump[secondDogeLoc].emplace(secondJump);

    for (int i=2; i<M; ++i) {
        int start, j;
        cin >> start >> j;
        jump[start].emplace(j);
    }
    adjList = vector<unordered_map<int, int>>(N, unordered_map<int,int>());
}

#define INF (int)2e9

vector<int> shortTime;

int dijkstra2()
{
    shortTime = vector<int>(N, INF);
    priority_queue<pair<int, int>> q;
    q.emplace(0, firstDogeLoc);
    shortTime[firstDogeLoc] = 0;
    while (!q.empty()) {
        auto [soFarDist, here] = q.top();
        soFarDist = -soFarDist;
        q.pop();

        if (shortTime[here] < soFarDist)
            continue;

        if (here == secondDogeLoc)
            return shortTime[here];

        for (int j : jump[here]) {
            // goto right
            for (int time=1, there=here+j*time; there < N; ++time, there=here+j*time ) {
                int destDist = soFarDist + time;
                if (shortTime[there] > destDist) {
                    shortTime[there] = destDist;
                    q.emplace(-destDist, there);
                }
            }

            //goto left
            for (int time=1, there=here-j*time; there >= 0; ++time, there=here-j*time ) {
                int destDist = soFarDist + time;
                if (shortTime[there] > destDist) {
                    shortTime[there] = destDist;
                    q.emplace(-destDist, there);
                }
            }
        }


    }
    return -1;
}


int dijkstraV2()
{
    shortTime = vector<int>(N, (int)2e9);
    vector<bool> visited(N, false);

    shortTime[firstDogeLoc] = 0;
    while (true) {
        int here = INF;
        int distHere = INF;
        for (int i=0; i<N; ++i) {
            if (shortTime[i] < distHere && !visited[i]) {
                here = i;
                distHere = shortTime[i];
            }
        }

        if (here == secondDogeLoc)
            return shortTime[here];

        if (distHere == INF)
            break;

        visited[here] = true;
        for (auto [there, dist] : adjList[here]) {
            int distThere = distHere + dist;
            if (!visited[there] && shortTime[there] > distThere) {
                shortTime[there] = distThere;
            }
        }
    }

    return -1;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("input.txt","r",stdin);
    input();
    cout << dijkstra2() << endl;

    return 0;
}

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