Submission #927885

#	Time	Username	Problem	Language	Result	Execution time	Memory
927885		AlphaMale06	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1018 ms	13140 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 sq=50;
const int inf = 1e9;
int dist[N];
bool mark[N];

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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.insert({0, s});
    while(st.size()){
        pair<int, int> nd = *st.begin();
        st.erase(nd);
        if(mark[nd.S] || dist[nd.S]<nd.F)continue;
        mark[nd.S]=1;
        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.insert({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.insert({dist[i], i});
                }
                cnt++;
            }
        }
        for(int i=0; i<nd.S; i++){
            for(int jump : small[nd.S]){
                int dv=divs[nd.S-i][jump];
                if(dv+nd.F<dist[i]){
                    dist[i]=dv+nd.F;
                    st.insert({dist[i], i});
                    break;
                }
            }
        }
        for(int i=nd.S+1; i<n; i++){
            for(int jump : small[nd.S]){
                int dv=divs[i-nd.S][jump];
                if(dv+nd.F<dist[i]){
                    dist[i]=dv+nd.F;
                    st.insert({dist[i], i});
                    break;
                }
            }
        }
    }
    if(dist[t]==inf)cout << -1 << '\n';
    else cout << dist[t] << '\n';
}

Compilation message (stderr)

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

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