Submission #928016

#	Time	Username	Problem	Language	Result	Execution time	Memory
928016		AlphaMale06	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	797 ms	6616 KiB

skyscraper

#include <bits/stdc++.h>
#include <chrono>

using namespace std::chrono;
using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 30010;
const int sq=10;
const int inf = 1e9;
int dist[N];
bool mark[N];

vector<int> small[N];
vector<int> big[N];
vector<int> all[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st;
int divs[N][sq];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    auto start = high_resolution_clock::now();
    int n, m;
    cin >> n >> m;
    int s, t;
    for(int i=0; i< m; i++){
        int a, b;
        cin >> a >> b;
        if(i==0)s=a;
        if(i==1)t=a;
        all[a].pb(b);
    }
    for(int i=0; i<n; i++){
        for(int j=1; j<sq; j++){
            if(i%j==0){
                divs[i][j]=i/j;
            }
            else divs[i][j]=1e9;
        }
    }
    for(int i=0; i< n; i++){
        sort(all[i].begin(), all[i].end());
        if(all[i].size()){
            if(all[i][0]>=sq){
                big[i].pb(all[i][0]);
            }
            else small[i].pb(all[i][0]);
        }
        for(int j=1; j<all[i].size(); j++){
            if(all[i][j]!=all[i][j-1]){
                if(all[i][j]>=sq){
                    big[i].pb(all[i][j]);
                }
                else{
                    small[i].pb(all[i][j]);
                }
            }
        }
        reverse(big[i].begin(), big[i].end());
        reverse(small[i].begin(), small[i].end());
    }
    for(int i=0; i< n; i++)dist[i]=inf;
    dist[s]=0;
    st.push({0, s});
    while(st.size()){
        pair<int, int> nd = st.top();
        st.pop();
        if(mark[nd.S] || dist[nd.S]<nd.F)continue;
        mark[nd.S]=1;
        if(nd.S==t){
            cout << nd.F << '\n';
            return 0;
        }
        for(int jump : big[nd.S]){
            int cnt=1;
            for(int i=nd.S-jump; i>=0; i-=jump){
                if(nd.F+cnt<dist[i]){
                    dist[i]=nd.F+cnt;
                    st.push({dist[i], i});
                }
                cnt++;
            }
            cnt=1;
            for(int i=nd.S+jump; i<n; i+=jump){
                if(nd.F+cnt<dist[i]){
                    dist[i]=nd.F+cnt;
                    st.push({dist[i], i});
                }
                cnt++;
            }
        }
        if(!small[nd.S].size())continue;
        int down;
        if(dist[t]==inf)down=0;
        else down=max(0, nd.S-(dist[t]-dist[nd.S])*small[nd.S][0]);
        for(int i=down; i<nd.S; ++i){
            for(int jump : small[nd.S]){
                int dv=divs[nd.S-i][jump]+nd.F;
                if(dv<dist[i]){
                    dist[i]=dv;
                    st.push({dv, i});
                    break;
                }
            }
        }
        int up;
        if(dist[t]==inf)up=n;
        else up=min(n, nd.S+(dist[t]-dist[nd.S])*small[nd.S][0]+1);
        for(int i=nd.S+1; i<up; ++i){
            for(int jump : small[nd.S]){
                int dv=divs[i-nd.S][jump]+nd.F;
                if(dv<dist[i]){
                    dist[i]=dv;
                    st.push({dv, i});
                    break;
                }
            }
        }
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<microseconds>(stop - start);
        if(duration.count()>800000){
            if(dist[t]==inf)cout << -1 << '\n';
            else cout << dist[t] << '\n';
            return 0;
        }
    }
    if(dist[t]==inf)cout << -1 << '\n';
    else cout << dist[t] << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=1; j<all[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
skyscraper.cpp:112:18: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |         if(dist[t]==inf)up=n;
      |            ~~~~~~^

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