제출 #716941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716941		Stickfish	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	337 ms	16480 KiB

skyscraper

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAXN = 30100;
const int SQN = 40;
const int INF = 1e9 + 177013;
pair<int, int> dogs[MAXN];
vector<int> jlen[MAXN];

bitset<MAXN> used;
int dist[MAXN][SQN];

void update(int i, int p, int d, set<pair<int, pair<int, int>>>& rdist) {
    if (dist[i][p] > d) {
        dist[i][p] = d;
        rdist.insert({d, {i, p}});
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> dogs[i].first >> dogs[i].second;
        jlen[dogs[i].first].push_back(dogs[i].second);
    }
    int s = dogs[0].first;
    int t = dogs[1].first;
    for (int i = 0; i < n; ++i) {
        for (int d = 0; d < SQN; ++d) {
            dist[i][d] = INF;
        }
    }
    dist[s][0] = 0;
    set<pair<int, pair<int, int>>> rdist;
    rdist.insert({0, {s, 0}});
    while (rdist.size()) {
        auto [d, ip] = *rdist.begin();
        auto [i, p] = ip;
        rdist.erase(rdist.begin());
        if (dist[i][p] < d)
            continue;
        update(i, 0, d, rdist);
        if (p == 0) {
            for (auto np : jlen[i]) {
                if (np < SQN) {
                    update(i, np, d, rdist);
                    continue;
                }
                for (int j = i % np; j < n; j += np) {
                    update(j, 0, d + abs(i - j) / np, rdist);
                }
            }
        } else {
            if (i >= p)
                update(i - p, p, d + 1, rdist);
            if (i + p < n)
                update(i + p, p, d + 1, rdist);
        }
    }
    if (dist[t][0] >= INF)
        cout << "-1\n";
    else
        cout << dist[t][0] << '\n';
}

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