Submission #124135

#	Time	Username	Problem	Language	Result	Execution time	Memory
124135		AyaBenSaad	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	468 ms	49348 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e3 + 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> > adj[M];
int dis[N][N], vis[N];
 
void Dijkstra (int u) {
  priority_queue <pair <long long, int> > q;
  vis[u]++;
  q.push ({-1, u});
  while (q.size()) {
    int x = q.top().second;
    q.pop();
    for (auto e : adj[x]) {
      int v = e.first;
      long long c = e.second;
      if ((!vis[v]) || vis [v] > c + vis[x]){
        vis[v] = c + vis[x];
        q.push({-vis[v], v});
      }
    }
  }
}
 
int main () {
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &b[i], &p[i]);
        for (int j = 0; j < n; j++) {
            if (abs(j-b[i]) % p[i] == 0) {
                if (dis[b[i]][j] == 0 || dis[b[i]][j] > abs(j-b[i]) / p[i]) dis[b[i]][j] = abs(j-b[i]) / p[i];
            }
        }  
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ( dis[i][j]) adj[i].push_back({j, dis[i][j]});
        }
    }
    Dijkstra(b[0]);
    if (vis[b[1]]) printf("%d\n", vis[b[1]]-1);
    else puts("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32: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:34: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: 21 / 21
• Subtask 5: 0 / 43