Submission #1235514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235514		tin_le	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	83 ms	11692 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define INF 1e18
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;

void solve() {
    int n, m; cin >> n >> m;
    int src = 0, dest = 0;
    vector<set<int>> g(n);
    for(int i = 0; i < m; i++) {
        int b, p; cin >> b >> p;
        g[b].insert(p);
        if(i == 0) src = b;
        else if(i == 1) dest = b;
    }
    priority_queue<pll, vector<pll>, greater<pll>> q;
    vll dp(n, INF);
    auto process = [&](int node, ll cost) -> void {
        if(dp[node] > cost) {
            dp[node] = cost;
            q.push({cost, node});
        }
    };
    process(src, 0);
    while(!q.empty()) {
        auto [cost, node] = q.top(); q.pop(); 
        if(dp[node] != cost) continue;
        if(node == dest) {
            cout << cost << '\n';
            return;
        }
        for(auto& dog : g[node]) {
            for(int u = node - dog, c = 1; u >= 0; u -= dog, c++) {
                process(u, cost + c);
                if(g[u].count(dog)) break;
            }
            for(int u = node + dog, c = 1; u < n; u += dog, c++) {
                process(u, cost + c);
                if(g[u].count(dog)) break;
            }
        }
    }
    cout << -1 << '\n';
}

signed main() {
    IOS;
    solve();
    return 0;
}

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