Submission #123987

#	Time	Username	Problem	Language	Result	Execution time	Memory
123987		AyaBenSaad	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	458 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3e4 + 3; //number of skyscrapers
const int M = 3e4 + 4; //number of doges;
const int inf = 1e9;

int n, m, b[M], p[M], ok;
vector <pair <int, int> > dgin[N], adj[M];
//int dp[M][N];
long long dis[N];
 
void Dijkstra (int u) {
  priority_queue <pair <int, int> > q;
  dis[u] ++;
  q.push ({-1, u});
  while (q.size()) {
    int x = q.top().second;
    q.pop();
    for (auto e : adj[x]) {
      int v = e.first;
      int c = e.second;
      if ((!dis[v]) || dis [v] > c + dis[x]){
        dis[v] = c + dis[x];
        q.push({-dis[v], v});
      }
    }
  }
}
 
int main () {
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &b[i], &p[i]);
       // dgin[b[i]].push_back (i);
        int a = b[i], k = 1;
        while (a-p[i] >= 0) {
            adj[b[i]].push_back ({a-p[i], k});
            k++;
            a -= p[i];
        }
        a = b[i], k = 1;
        while (a+p[i] < n) {
            adj[b[i]].push_back ({a+p[i], k});
            k++;
            a += p[i];
        }
    }
    /*memset (dp, -1, sizeof dp);
    int x = solve(0, b[0]);
    if(ok) printf("%d\n", x-1);
    else puts("-1");*/
    Dijkstra(b[0]);
    printf("%lld\n", dis[b[1]]-1);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:33:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &n, &m);
     ~~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &b[i], &p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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