Submission #928048

#	Time	Username	Problem	Language	Result	Execution time	Memory
928048		AlphaMale06	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	199 ms	4560 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

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

const int N = 30010;
const int inf = 1e9;
int dist[N];
int tot[N];
bool mark[N];
vector<int> all[N];
vector<int> jumps[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int cntl=0;
    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++){
        sort(all[i].begin(), all[i].end());
        if(all[i].size()){
            jumps[i].pb(all[i][0]);
            if(jumps[i].back()<=5)cntl++;
            for(int j=1; j<all[i].size(); j++){
                if(all[i][j]!=all[i][j-1]){
                    jumps[i].pb(all[i][j]);
                    if(jumps[i].back()<=5)cntl++;
                }
            }
        }
        reverse(jumps[i].begin(), jumps[i].end());
    }
    for(int i=0; i< n; i++){
        tot[i]=inf;
        for(int jump : jumps[i]){
            if(abs(i-t)%jump==0){
               tot[i]=abs(i-t)/jump;
               break;
            }
        }
    }
    for(int i=0; i< n; i++)dist[i]=inf;
    dist[s]=0;
    st.push({0, s});
    int num;
    if(n<=12400 || cntl<=12400)num=10000000;
    else num=12400;
    while(st.size() && num--){
        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 || nd.F>dist[t]){
            cout << dist[t] << '\n';
            return 0;
        }
        if(tot[nd.S]+nd.F<dist[t]){
            dist[t]=tot[nd.S]+nd.F;
        }
        for(int jump : jumps[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++;
                if(nd.F+cnt>=dist[t])break;
            }
            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(nd.F+cnt>=dist[t])break;
            }
        }
    }
    int ans=inf;
    for(int i=0; i< n; i++){
        ans=min(ans, tot[i]+dist[i]);
    }
    if(ans==inf)cout << -1 << '\n';
    else cout << ans << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for(int j=1; j<all[i].size(); j++){
      |                          ~^~~~~~~~~~~~~~
skyscraper.cpp:72:20: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |             dist[t]=tot[nd.S]+nd.F;
      |                    ^

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