Submission #568541

#	Time	Username	Problem	Language	Result	Execution time	Memory
568541		Ooops_sorry	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	441 ms	9652 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll long long

mt19937 rnd(51);

const int N = 30010, K = 50, INF = 1e9, M = 1e5 + 10;
int d[N][K];

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            d[i][j] = INF;
        }
    }
    int n, m;
    cin >> n >> m;
    vector<int> b(m), p(m), ans(n, INF);
    vector<vector<int>> need(n);
    for (int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        need[b[i]].pb(abs(p[i]));
    }
    ans[b[0]] = 0;
    set<array<int, 3>> st;
    st.insert({0, b[0], -1});
    while (st.size() > 0) {
        auto arr = *st.begin();
        st.erase(arr);
        int v = arr[1], j = arr[2];
        if (j == -1) {
            for (auto to : need[v]) {
                if (to < K) {
                    if (d[v][to] > ans[v]) {
                        st.erase({d[v][to], v, to});
                        d[v][to] = ans[v];
                        st.insert({d[v][to], v, to});
                    }
                } else {
                    for (int k = v, add = 0; k < n; k += to, add++) {
                        if (ans[k] > ans[v] + add) {
                            st.erase({ans[k], k, -1});
                            ans[k] = ans[v] + add;
                            st.insert({ans[k], k, -1});
                        }
                    }
                    for (int k = v, add = 0; k >= 0; k -= to, add++) {
                        if (ans[k] > ans[v] + add) {
                            st.erase({ans[k], k, -1});
                            ans[k] = ans[v] + add;
                            st.insert({ans[k], k, -1});
                        }
                    }
                }
            }
        } else {
            if (d[v][j] < ans[v]) {
                st.erase({ans[v], v, -1});
                ans[v] = d[v][j];
                st.insert({ans[v], v, -1});
            }
            if (v + j < n && d[v + j][j] > d[v][j] + 1) {
                st.erase({d[v + j][j], v + j, j});
                d[v + j][j] = d[v][j] + 1;
                st.insert({d[v + j][j], v + j, j});
            }
            if (v - j >= 0 && d[v - j][j] > d[v][j] + 1) {
                st.erase({d[v - j][j], v - j, j});
                d[v - j][j] = d[v][j] + 1;
                st.insert({d[v - j][j], v - j, j});
            }
        }
    }
    cout << (ans[b[1]] == INF ? -1 : ans[b[1]]) << endl;
    return 0;
}

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