Submission #107314

#	Time	Username	Problem	Language	Result	Execution time	Memory
107314		abil	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1065 ms	8064 KiB

skyscraper

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

priority_queue<pair<int,int >> q;
int b[N], p[N], vis[N];
vector<int > v[N];
main () {
      int n, m;
      cin >> n >> m;
      for(int i = 1;i <= m; i++){
            cin >> b[i] >> p[i];
            v[b[i]].pb(p[i]);
      }
      memset(vis, 0x3f3f3f3f, sizeof(vis));
      vis[b[1]] = 0;
      q.push(mk(0,b[1]));
      while(!q.empty()){
          pair<int,int > u = q.top();
          q.pop();
          if(u.fr != vis[u.sc]){
            continue;
          }
          for(auto i : v[u.sc]){
            int cnt = u.fr;
            for(int j = u.sc + i; j < n; j += i){
                  if(vis[j] > ++cnt){
                        q.push(mk(vis[j] = cnt,j));
                  }
            }
            cnt = u.fr;
            for(int j = u.sc - i; j >= 0; j -= i){
                  if(vis[j] > ++cnt){
                        q.push(mk(vis[j] = cnt,j));
                  }
            }
          }
      }
      int ans = vis[b[2]];
      cout << ((ans > 1e9) ? -1 : ans);
}

Compilation message (stderr)

skyscraper.cpp:21:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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