Submission #969786

#	Time	Username	Problem	Language	Result	Execution time	Memory
969786		Pring	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	92 ms	6604 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, pos[MXN], p[MXN];
int dis[MXN];
vector<int> v[MXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;

bool PUSH(int to, int len, int t) {
    if (len < dis[to]) {
        dis[to] = len;
        pq.push(mp(len, to));
    }
    auto it = lower_bound(v[to].begin(), v[to].end(), t);
    if (it != v[to].end() && *it == t) return false;
    return true;
}

void DIJKSTRA(int sr) {
    fill(dis, dis + n, INF);
    dis[sr] = 0;
    pq.push(mp(0, sr));
    while (pq.size()) {
        auto [len, id] = pq.top();
        pq.pop();
        if (dis[id] < len) continue;
        // dis[id] = len;
        if (id == pos[1]) break;
        for (auto &t : v[id]) {
            for (int i = 1; id + t * i < n; i++) {
                int to = id + t * i;
                if (!PUSH(to, len + i, t)) break;
            }
            for (int i = 1; id - t * i >= 0; i++) {
                int to = id - t * i;
                if (!PUSH(to, len + i, t)) break;
            }
        }
    }
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, m) {
        cin >> pos[i] >> p[i];
        v[pos[i]].push_back(p[i]);
    }
    FOR(i, 0, n) {
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
    }
    DIJKSTRA(pos[0]);
    cout << (dis[pos[1]] == INF ? -1 : dis[pos[1]]) << '\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: 43 / 43