Submission #564004

#	Time	Username	Problem	Language	Result	Execution time	Memory
564004		Cyanmond	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	637 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr i64 inf = 1ll << 50;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()
template <typename T> bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

vector<i64> calc_mincost(int S, vector<vector<pair<int, i64>>> &g) {
    const int N = (int)g.size();
    vector<i64> dist(N, inf);
    dist[S] = 0;
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> hp;
    hp.push({0, S});
    while (not hp.empty()) {
        const auto [nd, f] = hp.top();
        hp.pop();
        if (nd > dist[f]) continue;
        for (const auto &[t, c] : g[f]) {
            if (chmin(dist[t], nd + c)) {
                hp.push({dist[t], t});
            }
        }
    }
    return dist;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> A(M);
    REP(i, M) {
        cin >> A[i].first >> A[i].second;
        chmin(A[i].second, N);
    }
    int S = 0, T = 0;
    {
        const auto as = A[0], at = A[1];
        sort(ALL(A), [](auto a, auto b) {
            if (a.second != b.second) {
                return a.second < b.second;
            }
            return a.first < b.first;
        });
        REP(i, M) {
            if (A[i] == as) S = i;
            if (A[i] == at) T = i;
        }
    }
    vector<vector<pair<int, bool>>> lst(N);
    REP(i, M) {
        if ((not lst[A[i].first].empty()) and lst[A[i].first].back().first == A[i].second) {
            lst[A[i].first].back().second = true;
            continue;
        } else {
            lst[A[i].first].push_back({A[i].second, true});
        }
        int f = A[i].first % A[i].second;
        while (f < N) {
            if (lst[f].empty() or lst[f].back().first != A[i].second)
                lst[f].push_back({A[i].second, false});
            f += A[i].second;
        }
    }

    vector<int> size_r(N + 1);
    REP(i, N) size_r[i + 1] = size_r[i] + (int)lst[i].size();
    vector<vector<int>> press(N);
    REP(i, N) { REP(j, (int)lst[i].size()) press[i].push_back(lst[i][j].first); }

    auto get_key = [&](int i, int w) { return lower_bound(ALL(press[i]), w) - press[i].begin(); };

    const int V = size_r[N] + N;
    vector<vector<pair<int, i64>>> graph(V);
    REP(i, N) {
        for (const auto &[w, c] : lst[i]) {
            const int id = size_r[i] + get_key(i, w);
            graph[id].push_back({size_r[N] + i, 0});
            if (c) graph[size_r[N] + i].push_back({id, 0});
            const int l = i - w;
            if (l >= 0) {
                const int id2 = size_r[l] + get_key(l, w);
                graph[id2].push_back({id, 1});
                graph[id].push_back({id2, 1});
            }
        }
    }

    auto dist = calc_mincost(size_r[N] + A[S].first, graph);
    auto ans = dist[size_r[N] + A[T].first];
    if (ans == inf) ans = -1;
    cout << ans << endl;
}

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