Submission #124020

#	Time	Username	Problem	Language	Result	Execution time	Memory
124020		AyaBenSaad	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1088 ms	189868 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;
set <pair <int, int> > adj[M];
long long dis[N];
 
void Dijkstra (int u) {
  priority_queue <pair <long long, 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;
      long long 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) {
            pair <int, int> x = {a-p[i], 2e9};
            auto r = adj[b[i]].lower_bound({a-p[i], -1});
            if (r != adj[b[i]].end() && (*r).first == a-p[i]) 
                 {x = *r;  adj[b[i]].erase (r);}
            adj[b[i]].insert ({a-p[i], min(k, x.second)});
            k++;
            a -= p[i];
        }
        a = b[i], k = 1;
        while (a+p[i] < n) {
            pair <int, int> x = {a+p[i], 2e9};
            auto r = adj[b[i]].lower_bound({a+p[i], -1});
            if (r != adj[b[i]].end() && (*r).first == a+p[i]) 
                {x = *r; adj[b[i]].erase (r);}
            adj[b[i]].insert ({a+p[i], min(k, x.second)});
            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]);
    if (dis[b[1]]) printf("%lld\n", dis[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: 0 / 21
• Subtask 5: 0 / 43