제출 #169153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169153		Milki	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	4 ms	2556 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; i <= n; i += range){
    int nxt = i + range;
    if(nxt >= n) continue;

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

    E[pos].pb(point(nxt, cnt));
    cnt ++;
  }

  cnt = 1;
  for(int i = pos; i >= 0; i -= range){
    int nxt = i - range;
    if(nxt < 0) continue;

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

    E[pos].pb(point(nxt, cnt));
    cnt ++;
  }
}

int dijkstra(){
  priority_queue <point> Q;
  Q.push(point(0, start[0]));
  vector <int> d(n, -1);

  while(!Q.empty()){
    while(!Q.empty() && d[Q.top().second] != -1) Q.pop();
    if(Q.empty()) break;

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

    for(auto e : E[cvor]){
      int ncvor = e.first, ndist = e.second;
      if(d[ncvor] != -1) continue;
      Q.push(point( -(distance + ndist), ncvor));
    }
  }
  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(i == 1) continue;
    update(start[i], dist[i]);
  }
  cout << dijkstra();
}

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