Submission #1280890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280890		SSKMF	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	256 ms	327680 KiB

skyscraper

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

vector < pair <int , int> > adiacenta[60001];
int distanta[60001];

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

    int numar_noduri_1 , numar_noduri_2;
    cin >> numar_noduri_1 >> numar_noduri_2;

    for (int indice = 1 ; indice <= numar_noduri_2 ; indice++)
    {
        int inceput , termen;
        cin >> inceput >> termen;

        inceput++;
        for (int nod = inceput ; nod <= numar_noduri_1 ; nod += termen)
            { adiacenta[indice + numar_noduri_1].emplace_back(nod , (nod - inceput) / termen); }
        
        for (int nod = inceput - termen ; nod > 0 ; nod -= termen)
            { adiacenta[indice + numar_noduri_1].emplace_back(nod , (inceput - nod) / termen); }
        
        adiacenta[inceput].emplace_back(indice + numar_noduri_1 , 0);
    }
    
    for (int indice = 1 ; indice <= numar_noduri_1 + numar_noduri_2 ; indice++)
        { distanta[indice] = INT32_MAX; }

    priority_queue < pair <int , int> > candidati;
    candidati.emplace(distanta[numar_noduri_1 + 1] = 0 , numar_noduri_1 + 1);
    while (!candidati.empty())
    {
        const int nod = candidati.top().second;
        if (distanta[nod] != -candidati.top().first)
            { candidati.pop(); continue; }

        candidati.pop();
        for (auto& vecin : adiacenta[nod]) {
            if (distanta[vecin.first] > distanta[nod] + vecin.second)
                { candidati.emplace(-(distanta[vecin.first] = distanta[nod] + vecin.second) , vecin.first); }
        }
    }
    
    cout << (distanta[numar_noduri_1 + 2] == INT32_MAX ? -1 : distanta[numar_noduri_1 + 2]);
    return 0;
}

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