Submission #444890

#	Time	Username	Problem	Language	Result	Execution time	Memory
444890		JovanB	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	40 ms	70772 KiB

skyscraper

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

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

const int K = 100;
const int MAXN = 30000;

vector <pair <int, int>> graf[K*MAXN+5];
int dist[K*MAXN+5];

const int INF = 1000000000;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int d=1; d<=K; d++){
        for(int i=0; i+d<n; i++){
            graf[K*i+d].push_back({K*(i+d), 1});
            graf[K*i+d].push_back({K*(i+d) + d, 1});
        }
        for(int i=n-1; i-d>=0; i--){
            graf[K*i+d].push_back({K*(i-d), 1});
            graf[K*i+d].push_back({K*(i-d) + d, 1});
        }
    }
    while(m--){
        int x, d;
        cin >> x >> d;
        if(d <= K) graf[K*x].push_back({K*x+d, 0});
        else{
            for(int i=x+d; i<n; i+=d) graf[K*x].push_back({K*i, (i-x)/d});
            for(int i=x-d; i>=0; i--) graf[K*x].push_back({K*i, (x-i)/d});
        }
    }
    for(int i=1; i<n*K; i++) dist[i] = INF;
    set <pair <int, int>> q;
    q.insert({0, 0});
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for(auto pr : graf[v]){
            int c = pr.first, d = pr.second;
            if(dist[c] > dist[v] + d){
                q.erase({dist[c], c});
                dist[c] = dist[v] + d;
                q.insert({dist[c], c});
            }
        }
    }
    if(dist[K] == INF) cout << "-1\n";
    else cout << dist[K] << "\n";
    return 0;
}

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