Submission #444898

#	Time	Username	Problem	Language	Result	Execution time	Memory
444898		JovanB	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	487 ms	114152 KiB

skyscraper

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

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

const int K = 25;
const int MAXN = 30000;

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

const int INF = 1000000000;

int gde[MAXN+5];

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<n; i++) graf[K*i+d].push_back({K*i, 0});
        for(int i=0; i+d<n; i++) 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) + d, 1});
    }
    for(int j=0; j<m; j++){
        int x, d;
        cin >> x >> d;
        gde[j] = K*x;
        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-=d) graf[K*x].push_back({K*i, (x-i)/d});
        }
    }
    for(int i=0; i<n*K; i++) dist[i] = INF;
    dist[gde[0]] = 0;
    set <pair <int, int>> q;
    q.insert({0, gde[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[gde[1]] == INF) cout << "-1\n";
    else cout << dist[gde[1]] << "\n";
    return 0;
}

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