Submission #441698

#	Time	Username	Problem	Language	Result	Execution time	Memory
441698		julian33	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	129 ms	7720 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int mxN=3e4;

int n,m,p,b,dist[mxN],seen[mxN];
set<int> jump[mxN];

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    cin>>n>>m;
    for(int i=0;i<n;i++)
        dist[i]=1e9;
    int s,e;
    for(int i=0;i<m;i++){
        cin>>b>>p;
        if(i==0)
            s=b;
        if(i==1)
            e=b;
        jump[b].insert(p);
    }
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({0,s}); dist[s]=0;
    while(!q.empty()){
        int at=q.top().second; q.pop();
        if(at==e)
            break;
        if(seen[at])
            continue;
        seen[at]=1;
        // cout<<at<<"\n";
        for(int i:jump[at]){
            for(int j=1;j<=n;j++){
                if(at+i*j>=n)
                    break;
                if(dist[at]+j<dist[at+i*j]){
                    dist[at+i*j]=dist[at]+j;
                    q.push({dist[at+i*j],at+i*j});
                }
                if(jump[at+i*j].count(i))
                    break;
            }
            for(int j=1;j<=n;j++){
                if(at-i*j<0)
                    break;
                if(dist[at]+j<dist[at-i*j]){
                    dist[at-i*j]=dist[at]+j;
                    q.push({dist[at-i*j],at-i*j});
                }
                if(jump[at-i*j].count(i))
                    break;
            }
        }
    }
    cout<<(dist[e]==1e9?-1:dist[e])<<"\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:27: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     q.push({0,s}); dist[s]=0;
      |                    ~~~~~~~^~
skyscraper.cpp:68:18: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     cout<<(dist[e]==1e9?-1:dist[e])<<"\n";
      |            ~~~~~~^

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