제출 #969759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969759		Pring	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	891 ms	54276 KiB

skyscraper

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 30005, INF = 1e9;
int n, m;
vector<int> pos, p;

namespace GRAPH {
    vector<int> bck[MXN];
    unordered_map<int, int> dis;
    unordered_map<int, bool> b;
    deque<int> dq;

    void ZOBFS(int sr, int to) {
        auto PUSH = [&](int id) -> void {
            auto PUT = [&](int i, int id, int w) -> void {
                if (b[i]) return;
                if (dis.find(i) == dis.end() || dis[i] < dis[id] + w) {
                    dis[i] = dis[id] + w;
                    if (w) dq.push_back(i);
                    else dq.push_front(i);
                }
            };
            if (id < n) {
                for (auto &i : bck[id]) PUT(i + n, id, 0);
                return;
            }
            if (id < n + m) {
                PUT(pos[id - n], id, 0);
                PUT(pos[id - n] * MXN + p[id - n] + n + m, id, 0);
                return;
            }
            id -= (n + m);
            int now = id / MXN, mod = id % MXN;
            PUT(now, id + n + m, 0);
            if (now - mod >= 0) PUT((now - mod) * MXN + mod + n + m, id + n + m, 1);
            if (now + mod < n) PUT((now + mod) * MXN + mod + n + m, id + n + m, 1);
        };
        dis[sr] = 0;
        dq.push_back(sr);
        int t = clock();
        while (dq.size() && clock() - t <= CLOCKS_PER_SEC / 10 * 7) {
            int id = dq.front();
            dq.pop_front();
            if (b[id]) continue;
            b[id] = true;
            PUSH(id);
            if (dis.find(to) != dis.end()) break;
        }
    }
}

int minimum_jumps(int N, int M, vector<int> &B, vector<int> &P) {
    using namespace GRAPH;
    n = N;
    m = M;
    pos = B;
    p = P;
    FOR(i, 0, m) bck[B[i]].push_back(i);
    ZOBFS(n, n + 1);
    if (dis.find(n + 1) == dis.end()) return -1;
    return dis[n + 1];
}

void miku() {
    int n, m;
    cin >> n >> m;
    vector<int> b(m), p(m);
    FOR(i, 0, m) cin >> b[i] >> p[i];
    cout << minimum_jumps(n, m, b, p) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

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