Submission #387169

#	Time	Username	Problem	Language	Result	Execution time	Memory
387169		kevinxiehk	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	158 ms	13276 KiB

skyscraper

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define sint long long
#define int long long
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    sint n,m,t,tt,s,e;cin>>n>>m;
    int dist[n+5],minadd[n+5];
    vector<sint>conn[n+5];
    set<sint>con2[n+5];
    memset(dist,-1,sizeof dist);
    memset(minadd,-1,sizeof minadd);
    int mtt=0;
    for(int i=0;i<m;i++){
        cin>>t>>tt;
        mtt=max(mtt,tt);
        if(i==0)s=t;
        if(i==1)e=t;
        if(tt!=0)con2[t].insert(tt);
    }
    if(mtt==1){
        cout<<abs(s-e)<<'\n';
        return 0;
    }
    for(int i=0;i<n;i++){
        for(auto&x:con2[i])conn[i].pb(x);
    }
    priority_queue<pair<int,sint>,vector<pair<int,sint>>,greater<>>dij;
    dij.push(mp(0,s));
    while(!dij.empty()){
        sint now=dij.top().se;
        if(dist[now]!=-1){dij.pop();continue;}
        dist[now]=dij.top().fi;
        dij.pop();
        for(auto x:conn[now]){
            //cout<<x;
            int nnow=now-now/x*x;
            while(nnow<n){
                if(now==nnow){nnow+=x;continue;}
                if(dist[nnow]==-1){
                    int di=dist[now]+abs(now-nnow)/x;
                    //cout<<x<<dist[now]+abs(i)<<" "<<minadd[now+i*x];
                    if(di<minadd[nnow]||minadd[nnow]==-1){
                        dij.push(mp(di,nnow));
                        minadd[nnow]=di;
                    }
                }
                nnow+=x;
            }
        }
    }
    //for(int i=0;i<n;i++)cout<<dist[i]<<" ";
    cout<<dist[e]<<"\n";
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59:17: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     cout<<dist[e]<<"\n";
      |                 ^

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