Submission #887938

#	Time	Username	Problem	Language	Result	Execution time	Memory
887938		Perl32	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	718 ms	4072 KiB

skyscraper

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int INF = (int) 1e9 + 1e3;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> m >> n;
    vector<pair<int, int>> a(n);
    vector<vector<int>> g(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
        g[a[i].first].push_back(a[i].second);
    }
    vector<int> dist(m, INF);
    set<pair<int, int>> st;
    st.insert({0, a[0].first});
    dist[a[0].first] = 0;
    while (!st.empty()) {
        auto [t, v] = *st.begin();
        st.erase(st.begin());
        for (auto jmp : g[v]) {
            int d = 0, cur = v;
            while (cur < m) {
                if (dist[cur] > dist[v] + d) {
                    st.erase({dist[cur], cur});
                    dist[cur] = dist[v] + d;
                    st.insert({dist[cur], cur});
                }
                cur += jmp;
                d++;
            }
            cur = v;
            d = 0;
            while (cur > -1) {
                if (dist[cur] > dist[v] + d) {
                    st.erase({dist[cur], cur});
                    dist[cur] = dist[v] + d;
                    st.insert({dist[cur], cur});
                }
                cur -= jmp;
                d++;
            }
        }
    }
    cout << (dist[a[1].first] == INF ? -1 : dist[a[1].first]);
}

/*

 */

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int32_t, char**)':
skyscraper.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto [t, v] = *st.begin();
      |              ^

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