Submission #100562

#	Time	Username	Problem	Language	Result	Execution time	Memory
100562		Extazy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1075 ms	3360 KiB

skyscraper

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 30007, INF = (1e9) + 7;

struct el {
  int to, cost;

  el() {}
  el(int a, int b): to(a), cost(b) {}

  bool operator <(const el &a) const {
    return cost > a.cost;
  }
};

int n, m, start[N], jump[N], dist[N];
vector < int > v[N];

void dijkstra() {
  priority_queue < el > q;
  el curr;
  int i, j, current_distance;

  fill(dist, dist + n, INF);

  dist[start[0]] = 0;
  q.push(el(start[0], 0));

  while(!q.empty()) {
    curr = q.top();
    q.pop();

    if(curr.cost!=dist[curr.to]) continue;
    
    for(i=0;i<(int)(v[curr.to].size());i++) {
      for(j=1;curr.to+j*v[curr.to][i]<n;j++) {
        current_distance = curr.cost + j;

        if(current_distance<dist[curr.to+j*v[curr.to][i]]) {
          dist[curr.to+j*v[curr.to][i]] = current_distance;
          q.push(el(curr.to+j*v[curr.to][i], current_distance));
        }
      }

      for(j=-1;curr.to+j*v[curr.to][i]>=0;j--) {
        current_distance = curr.cost - j;

        if(current_distance<dist[curr.to+j*v[curr.to][i]]) {
          dist[curr.to+j*v[curr.to][i]] = current_distance;
          q.push(el(curr.to+j*v[curr.to][i], current_distance));
        }
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;

  scanf("%d %d", &n, &m);
  for(i=0;i<m;i++) {
    scanf("%d %d", &start[i], &jump[i]);
    v[start[i]].push_back(jump[i]);
  }

  dijkstra();

  printf("%d\n", dist[start[1]]==INF ? -1 : dist[start[1]]);

  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &start[i], &jump[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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