Submission #1240942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240942		altern23	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	447 ms	65884 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 5e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;

map<pii, bool> vis[2];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, m; cin >> n >> m;
        vector<ll> b(m + 5), p(m + 5);
        for(int i = 1; i <= m; i++) cin >> b[i] >> p[i];
        vector<pii> adj[n + 5];
        for(int i = 1; i <= m; i++){
            ll cur = 0;
			for(int j = b[i] + p[i]; j < n; j += p[i]){
				adj[b[i]].push_back({j, ++cur});
				if(vis[0][{j, p[i]}]) break;
				vis[0][{j, p[i]}] = 1;
			}
			cur = 0;
			for(int j = b[i] - p[i]; j >= 0; j -= p[i]){
				adj[b[i]].push_back({j, ++cur});
				if(vis[1][{j, p[i]}]) break;
				vis[1][{j, p[i]}] = 1;
			}
        }
        
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<ll> dp(n + 5, INF);
        dp[b[1]] = 0;
        pq.push({dp[b[1]], b[1]});
        for(;!pq.empty();){
            auto [dist, idx] = pq.top(); pq.pop();
            if(dist > dp[idx]) continue;
            for(auto [i, j] : adj[idx]){
                if(dp[i] > dist + j){
                    dp[i] = dist + j;
                    pq.push({dp[i], i});
                }
            }
        }

        cout << (dp[b[2]] == INF ? -1 : dp[b[2]]) << "\n";
    }   
}

/*

*/ 

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