Submission #169542

#	Time	Username	Problem	Language	Result	Execution time	Memory
169542		Milki	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1085 ms	124884 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];
bool S[MAXN][1000];
vector <point> E[MAXN];

struct Edge{
  int x, cost;
  Edge(){}
  Edge(int x, int cost) : x(x), cost(cost) {}

  friend bool operator < (const Edge &A, const Edge &B){
    return A.cost > B.cost;
  }
};

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(range < 1000 && S[i][range] == true) break;
  }

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

    if(range < 1000 && S[i][range] == true) break;
  }
}

unordered_set <int> ubaci[MAXN];

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

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

    auto edge = Q.top();
    d[edge.x] = edge.cost;

    if(edge.x == start[1]) break;

    for(auto it : ubaci[edge.x])
      update(edge.x, it);

    for(auto e : E[edge.x]){
      int ncvor = e.first, ndist = e.second;
      if(d[ncvor] != -1) continue;
      Q.push(Edge( ncvor, edge.cost + ndist ));
    }
  }
  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){
    ubaci[start[i]].insert(dist[i]);
    if(dist[i] < 500)
      S[start[i]][dist[i]] = 1;
  }

  cout << dijkstra();
}

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