Submission #1210147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210147		anfi	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	543 ms	10028 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e18;

signed main(){
    int n,m; cin >> n >> m;
    int ans = 0, en = 0;
    vector<int> adj[n+7];
    vector<int> vis(n+7, inf);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for(int i = 0; i < m; i++){
        int u,v; cin >> u >> v; u++;
        adj[u].push_back(v);
        if(i == 0) {pq.push({0LL, u}); vis[u] = 0;}
        if(i == 1) en = u;
    }
    for(int i = 1; i <= n; i++){
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }

    while(!pq.empty()){
        auto [di ,nw] = pq.top(); pq.pop();
        if(nw == en){
            cout << vis[nw] << "\n"; exit(0);
        }
        if(di > vis[nw]) continue;
        for(int p : adj[nw]){
            int anfi = 1;
            for(int i = p+nw; i <= n; i += p){
                if(vis[i] > vis[nw]+anfi){
                    vis[i] = vis[nw]+anfi;                    
                    pq.push({vis[i], i});
                }
                anfi++;
            }
            anfi = 1;
            for(int i = nw-p; i >= 1; i-= p){
                if(vis[i] > vis[nw]+anfi){
                    vis[i] = vis[nw]+anfi;                    
                    pq.push({vis[i],i});
                }
                anfi++;
            }
        }
    }
    cout << "-1\n";
}

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