Submission #169593

#	Time	Username	Problem	Language	Result	Execution time	Memory
169593		Milki	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	264 ms	64756 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int MAXN = 3e4 + 5;

int n, m, dist[MAXN], start[MAXN];
set<int> S[MAXN];
vector <point> E[MAXN];

void update(int pos, int range){
  int cnt = 1;
  for(int i = pos + range; i < n; i += range){
    E[pos].pb(point(i, cnt));
    cnt ++;

    if(S[i].find(range) != S[i].end()) break;
  }

  cnt = 1;
  for(int i = pos - range; i >= 0; i -= range){
    E[pos].pb(point(i, cnt));
    cnt ++;

    if(S[i].find(range) != S[i].end()) break;
  }
}

const int inf = 1e9;

int dijkstra(){
  priority_queue <point> Q;
  Q.push(point(0, start[0]));
  vector <int> d(MAXN, inf);
  d[start[0]] = 0;

  while(!Q.empty()){
    auto tmp = Q.top(); Q.pop();
    int distance = -tmp.first;
    int cvor = tmp.second;
    d[cvor] = distance;

    if(cvor == start[1]) break;

    for(auto e : E[cvor]){
      int ncvor = e.first;
      int ndist = distance + e.second;
      if(ndist < d[ncvor]){
        d[ncvor] = ndist;
        Q.push(point(-ndist, ncvor));
      }
    }
  }
  if(d[start[1]] == inf) return -1;
  else return d[start[1]];
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> m;
  REP(i, m)
    cin >> start[i] >> dist[i];
  REP(i, m)
    if(start[i] != start[1])
      S[start[i]].insert(dist[i]);

  REP(i, n){
    if(i == start[1]) continue;
    for(auto it : S[i])
      update(i, it);
  }
  cout << dijkstra();
}

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