Submission #577330

#	Time	Username	Problem	Language	Result	Execution time	Memory
577330		MohamedFaresNebili	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	464 ms	112904 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
        using pi = array<int, 3>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        #define ub upper_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int N, M;
        int B[30001], P[30001];
        vector<int> S[30001];
        bitset<30001> vis[30001];

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> M;
            for(int l = 0; l < M; l++) {
                cin >> B[l] >> P[l];
                S[B[l]].pb(P[l]);
            }
            vector<int> d(N, 1e9 + 7);
            queue<pi> q; q.push({B[0], 0, 0});
            while(!q.empty()) {
                int A = q.front()[0], W = q.front()[1];
                int J = q.front()[2]; q.pop();
                if(A == B[1]) {
                    cout << W << "\n";
                    return 0;
                }
                if(A + J < N && !vis[A][A + J]) {
                    q.push({A + J, W + 1, J});
                    vis[A][A + J] = 1;
                }
                if(A - J >= 0 && !vis[A][A - J]) {
                    q.push({A - J, W + 1, J});
                    vis[A][A - J] = 1;
                }
                for(auto U : S[A]) {
                    if(A + U < N && !vis[A][A + U]) {
                        q.push({A + U, W + 1, U});
                        vis[A][A + U] = 1;
                    }
                    if(A - U >= 0 && !vis[A][A - U]) {
                        q.push({A - U, W + 1, U});
                        vis[A][A - U] = 1;
                    }
                }
            }

            cout << -1 << "\n";
            return 0;
        }

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