Submission #169348

#	Time	Username	Problem	Language	Result	Execution time	Memory
169348		Milki	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1072 ms	53496 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];
unordered_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;
  }
}

int dijkstra(){
  priority_queue <point> Q;
  Q.push(point(0, start[0]));
  vector <int> d(MAXN, -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;

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

    for(auto it : S[cvor])
      update(cvor, it);

    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(start[i] != start[1])
      S[start[i]].insert(dist[i]);

  cout << dijkstra();
}

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