Submission #883440

#	Time	Username	Problem	Language	Result	Execution time	Memory
883440		SalihSahin	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	222 ms	262144 KiB

skyscraper

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
 
using namespace std;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e3 + 5;

vector<vector<int> >  dis(N, vector<int>(N, inf));

int32_t main(){
    ios_base::sync_with_stdio(false), cin.tie();
    int n, m;
    cin>>n>>m;
    int start, finish;
    for(int i = 0; i < m; i++){
        int b, p;
        cin>>b>>p;
        if(i == 0) start = b;
        if(i == 1) finish = b;

        for(int k = b%p; k < n; k += p){
            dis[b][k] = min(dis[b][k], abs(b - k)/p);
        }
    }
    vector<pair<int, int> > adj[N];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j || dis[i][j] == inf) continue;
            adj[i].pb(mp(j, dis[i][j]));
        }
    }

    priority_queue<pair<int, int> > pq;
    vector<int> best(N, inf);
    best[start] = 0;
    pq.push(mp(0, start));
    int ans = -1;
    while(pq.size()){
        int node = pq.top().second;
        int len = pq.top().first * (-1);
        pq.pop();
        best[node] = len;
        if(node == finish){
            ans = len;
            break;
        }

        for(auto itr: adj[node]){
            if(best[itr.first] > best[node] + itr.second){
                pq.push(mp(-(best[node] + itr.second), itr.first));
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:38:15: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |     best[start] = 0;
      |               ^
skyscraper.cpp:46:9: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |         if(node == finish){
      |         ^~

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