Submission #169329

#	Time	Username	Problem	Language	Result	Execution time	Memory
169329		Milki	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	563 ms	48648 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, d[MAXN], dist[MAXN], start[MAXN];
vector <point> E[MAXN];
set<int> S[MAXN];

void update(int pos, int range){
  int cnt = 1;
  for(int curr = pos + range; curr < n; curr += range){
    if(S[curr].find(range) != S[curr].end()) break;
    S[curr].insert(range);

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

  cnt = 1;
  for(int curr = pos - range; curr >= 0; curr -= range){
    if(S[curr].find(range) != S[curr].end()) break;
    S[curr].insert(range);

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

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

  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 edge : E[cvor]){
      int ncvor = edge.first, ndist = edge.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)
      update(start[i], dist[i]);

  cout << dijkstra();
}

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