Submission #1230280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230280		marselel	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	9 ms	2632 KiB

skyscraper

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


using ll = long long;
using ld = long double;

# define all(a) a.begin(), a.end()
# define rall(a) a.rbegin(), a.rend()
# define pii pair<int, int>
# define pll pair<ll, ll>
#ifdef LOCAL
#include "algo/debug.h"
#else
# define debug(x)
#endif
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 2e15;
const ld RANDMAX = (1LL << 32) - 1;
const ll mod = 1'000'000'007;


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


const int maxn = 30'010;
vector<pii> g[maxn];



void solve() {
    int n, m; cin >> n >> m;
    vector<pii> a[n];
    int first = -1;
    int second = -1;
    for (int i = 0; i < m; ++i) {
        int b, p; cin >> b >> p;
        if (i == 0) {
            first = b;
        }
        if (i == 1) {
            second = b;
        }
        a[b].push_back({i, p});
    }
    if (first == second) {
        cout << 0;
        return;
    }
    for (int i = 0; i < n; ++i) {
        for (auto [ind, p] : a[i]) {
            for (int j = i + p; j < n; j += p) {
                for (auto [ind2, _] : a[j]) {
                    g[ind].push_back({ind2, (j - i) / p});
                    debug(ind);
                    debug(ind2);
                }   
            }
            for (int j = i  - p; j >= 0; j -= p) {
                for (auto [ind2, _] : a[j]) {
                    g[ind].push_back({ind2, (i - j) / p});
                    debug(ind);
                    debug(ind2);
                }   
            }
        }
    }
    vector<int> dist(m, inf);
    vector<bool> used(m);
    dist[0] = 0;
    for (int i = 0; i < m; ++i) {
        int v = -1;
        debug(dist);
        for (int j = 0; j < m; ++j) {
            if (!used[j] && (v == -1 || dist[j] < dist[v])) {
                v = j;
            }
        }
        debug(v);
        if (dist[v] == inf) {
            cout << -1;
            return;
        }
        used[v] = 1;
        for (auto [to, w] : g[v]) {
            if (dist[to] > dist[v] + w) {
                dist[to] = dist[v] + w;
            } 
        }
    }
    if (dist[1] == inf) {
        cout << -1;
    } else { 
        cout << dist[1];
    }
        
}













signed main() {
#ifdef LOCAL
    (void)!freopen("input.txt", "r", stdin);
#else
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
#endif
    int tt = 1;
    //cin >> tt;
/*  Бисмил ляяхи ррахмаани ррахиим.
    Изаа джаа’э насрул лаахи валь фатх.
    Ва ра’этэ нааса ядхулююнэ фии дии нил ляяхи афвааджа.
    Фа саббих би хамди раббикя вастагфирхь.
    Иннаху кяяна тавваабэ

    Бисмил ляяхи ррахмаани ррахиим.
    Куль а‘уузу би раббин наас.
    Мааликин наас.
    Иляяхин наас.
    Мин шарриль васваасиль ханнаас.
    Аллязии ювасвису фии судуурин наас. Миналь джиннати ван наас

    Бисмил ляяхи ррахмаани ррахиим.
    Куль яяайюхэль кяяфируун.
    Ляя а‘буду маа та‘будуун.
    Ва ляя энтум ‘аабиду унэ маа а‘буд.
    Ва ляя ана ‘аабидум маа ‘абадтум. Ва ляя энтум ‘аабидуунэ маа а‘буд.
    Лякум диинукум ва лияд диин
*/
    while (tt--) {
        solve();
        cout << '\n';
    }
    cerr << "\nRuntime = " << ((ld)clock() / CLOCKS_PER_SEC) << " ms\n";
}

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