Submission #66658

#	Time	Username	Problem	Language	Result	Execution time	Memory
66658		tincamatei	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	201 ms	112820 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 30000;

bitset<MAX_N> doges[MAX_N];
vector<int> scrapers[MAX_N];

int dist[MAX_N];
int doggoB[MAX_N], doggoP[MAX_N];

int dijkstra(int n, int src, int dest) {
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  memset(dist, 0x3f3f3f3f, sizeof(dist));
  dist[src] = 0;
  pq.push(make_pair(0, src));
  while(!pq.empty()) {
    int nod = pq.top().second, distNod = pq.top().first;
    pq.pop();

    if(distNod == dist[nod]) {
      if(nod == dest)
        return distNod;

      for(auto dog: scrapers[nod]) {
        int it = nod - dog, cost = 1;
        while(it >= 0) {
          if(dist[nod] + cost < dist[it]) {
            dist[it] = dist[nod] + cost;
            pq.push(make_pair(dist[it], it));
          }
          if(doges[it][dog])
            break;

          it -= dog;
          ++cost;
        }
        it = nod + dog, cost = 1;
        while(it < n) {
          if(dist[nod] + cost < dist[it]) {
            dist[it] = dist[nod] + cost;
            pq.push(make_pair(dist[it], it));
          }
          if(doges[it][dog])
            break;
          it += dog;
          ++cost;
        }
      }
    }
  }

  return -1;
}

int main() {
  int n, m, b, p;
  scanf("%d%d", &n, &m);

  for(int i = 0; i < m; ++i) {
    scanf("%d%d", &b, &p);
    doggoB[i] = b;
    doggoP[i] = p;
    if(!doges[b][p]) {
      scrapers[b].push_back(p);
      doges[b][p] = true;
    }
  }

  printf("%d", dijkstra(n, doggoB[0], doggoB[1]));
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59: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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &b, &p);
     ~~~~~^~~~~~~~~~~~~~~~

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