Submission #975811

#	Time	Username	Problem	Language	Result	Execution time	Memory
975811		andro	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	158 ms	69688 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];
bool mark[N];
set<int> jumps[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st;
vector<pair<int, int>> adj[N];
 
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;
        jumps[a].insert(b);
    }
    for(int i=0; i< n; i++){
        for(auto jump : jumps[i]){
            int cnt=1;
            for(int j=i-jump; j>=0; j-=jump){
                adj[i].pb({j, cnt});
                cnt++;
                if(jumps[j].find(jump)!=jumps[j].end())break;
            }
            cnt=1;
            for(int j=i+jump; j<n; j+=jump){
                adj[i].pb({j, cnt});
                cnt++;
                if(jumps[j].find(jump)!=jumps[j].end())break;
            }
        }
    }
    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;
        for(auto to : adj[nd.S]){
            if(to.S+nd.F<dist[to.F]){
                dist[to.F]=to.S+nd.F;
                st.push({dist[to.F], to.F});
            }
        }
    }
    if(dist[t]==inf)cout << -1 << '\n';
    else cout << dist[t] << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:62:14: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     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: 43 / 43