제출 #60624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60624		Flugan42	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1055 ms	6884 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,_,mindist;
vector<vi> dog;
vector<set<ll> > jumps;
set<ll> __;

int main(){
  cin >> n >> m; b.assign(m,0); p.assign(m,0);
  jumps.assign(n,__);
  rep(i,0,m) {
    cin >> b[i] >> p[i];
    jumps[b[i]].insert(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]));
  mindist.assign(n,inf);

  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;
    trav(px,jumps[i]){
      ll cur = i+px,cnt = 1;
      while (cur < n) {
        if (!vis[cur] && mindist[cur] > dist+cnt && sz(dog[cur]) > 0) {
          pq.push(make_pair(-dist-cnt,cur));
          mindist[cur] = dist+cnt;
        }
        cur += px; cnt++;
      }
      cur = i-px, cnt = 1;
      while (cur >= 0){
        if (!vis[cur] && mindist[cur] > dist+cnt && sz(dog[cur]) > 0) {
          pq.push(make_pair(-dist-cnt,cur));
          mindist[cur] = dist+cnt;
        }
        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