Submission #60593

#	Time	Username	Problem	Language	Result	Execution time	Memory
60593		Flugan42	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1046 ms	263168 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9223372036854775807
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)

ll n,m;
vi b,p,vis,_;
vector<vi> dog;

int main(){
  cin >> n >> m; b.assign(m,0); p.assign(m,0);
  rep(i,0,m) cin >> b[i] >> p[i];
  dog.assign(n,_);
  rep(i,0,m) dog[b[i]].push_back(i);
  vis.assign(n,0);
  priority_queue<ii> pq;
  pq.push(make_pair(0,b[0]));
  while (!pq.empty()){
    ll dist = -pq.top().first, i = pq.top().second; pq.pop();
    if (i == b[1]) {
      cout << dist << endl;
      exit(0);
    }
    if (vis[i]) continue;
    vis[i] = 1;
    rep(j,0,sz(dog[i])){
      ll px = p[dog[i][j]],cur = i+px,cnt = 1;
      while (cur < n) {
        if (!vis[cur]) pq.push(make_pair(-dist-cnt,cur));
        cur += px; cnt++;
      }
      cur = i-px, cnt = 1;
      while (cur >= 0){
        if (!vis[cur]) pq.push(make_pair(-dist-cnt,cur));
        cur -= px; cnt++;
      }
    }
  }
  cout << -1 << endl;
}

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