Submission #107902

#	Time	Username	Problem	Language	Result	Execution time	Memory
107902		dfistric	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1072 ms	65528 KiB

skyscraper

#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int MAXN = 30010;
ll B[MAXN], P[MAXN];
int n, m;
vector <pair <int, ll> > ve[MAXN];
set <pair <ll, int> > se;
ll dist[MAXN];
int bio[MAXN];

int main() {
    ios_base::sync_with_stdio(false);

    cin >> n >> m;

    REP(i, m) cin >> B[i] >> P[i];

    REP(i, m) {
        REP(j, m) {
            if (i == j) continue;

            if (abs(B[i] - B[j]) % P[i] == 0) ve[i].push_back({j, abs(B[i] - B[j]) / P[i]});
        }
    }

    FOR(i, 1, m) dist[i] = (1LL << 60);
    REP(i, m) se.insert({dist[i], i});
    
    while (se.size()) {
        auto tr = *se.begin();
        se.erase(se.begin());

        int x = tr.second;
        ll D = tr.first;
        bio[x] = 1;

        if (x == 1) continue;

        for (auto t : ve[x]) {
            int y = t.first;
            ll d = t.second;
            if (dist[y] > D + d) {
                assert(bio[y] == 0);

                se.erase({dist[y], y});
                dist[y] = D + d;
                se.insert({dist[y], y});
            }
        }
    }

    if (dist[1] >= (1LL << 60)) cout << "-1\n";
    else                        cout << dist[1] << "\n";

    return 0;
}

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