Submission #100569

#	Time	Username	Problem	Language	Result	Execution time	Memory
100569		Extazy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	902 ms	2808 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];
bool in[N];

void spfa() {
  queue < int > q;
  int i, j, curr, current_distance;

  fill(dist, dist + n, INF);
  
  dist[start[0]] = 0;
  q.push(start[0]);
  in[start[0]] = true;

  while(!q.empty() && clock()<=0.90*CLOCKS_PER_SEC) {
    curr = q.front();
    q.pop();
    in[curr] = false;

    for(i=0;i<(int)(v[curr].size()) && clock()<=0.90*CLOCKS_PER_SEC;i++) {
      for(j=1;curr+j*v[curr][i]<n;j++) {
        current_distance = dist[curr] + j;

        if(current_distance<dist[curr + j*v[curr][i]]) {
          dist[curr + j*v[curr][i]] = current_distance;
          
          if(!in[curr + j*v[curr][i]]) {
            q.push(curr + j*v[curr][i]);
            in[curr + j*v[curr][i]] = true;
          }
        }
      }
      
      for(j=-1;curr+j*v[curr][i]>=0;j--) {
        current_distance = dist[curr] - j;

        if(current_distance<dist[curr + j*v[curr][i]]) {
          dist[curr + j*v[curr][i]] = current_distance;
          
          if(!in[curr + j*v[curr][i]]) {
            q.push(curr + j*v[curr][i]);
            in[curr + j*v[curr][i]] = true;
          }
        }
      }
    }
  }
}

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]);
  }

  spfa();

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

  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111: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:113: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: 43 / 43