Submission #304733

#	Time	Username	Problem	Language	Result	Execution time	Memory
304733		rocks03	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	687 ms	3956 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;

const int MAXN = 3e4+100;
int N, M, S, E, B[MAXN], P[MAXN];
vector<int> adj[MAXN];

void read(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> B[i] >> P[i];
        adj[B[i]].pb(P[i]);
    }
    S = B[0], E = B[1];
}

void solve(){
    read();
    vector<int> dp(N, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, S});
    dp[S] = 0;
    while(!pq.empty()){
        int dist = pq.top().ff;
        int v = pq.top().ss;
        pq.pop();
        if(dp[v] < dist){
            continue;
        }
        if(v == E) break;
        for(auto p : adj[v]){
            for(int u = v + p, w = 1; u < N; u += p, w++){
                if(dp[u] > dp[v] + w){
                    dp[u] = dp[v] + w;
                    pq.push({dp[u], u});
                }
            }
            for(int u = v - p, w = 1; u >= 0; u -= p, w++){
                if(dp[u] > dp[v] + w){
                    dp[u] = dp[v] + w;
                    pq.push({dp[u], u});
                }
            }
        }
    }
    if(dp[E] == INT_MAX){
        dp[E] = -1;
    }
    cout << dp[E];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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