Submission #1192089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192089		emad234	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	470 ms	271384 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 3e4 + 5;
using namespace std;
struct node{
  int q,p;
};
vector<pair<node,int>>v[mxN][100];
int pos[mxN];
int dist[mxN][100];
bool operator<(pair<node,int>a,pair<node,int>b){
  return a.S > b.S;
}
signed main(){
  int n,m;
  cin >>n>>m;
  int buck = 99;
  for(int p = 1;p <= buck;p++){
    for(int i = 0;i < n;i++){
      if(i + p < n){
        v[i][p].push_back({{i + p,p},1});
        v[i + p][p].push_back({{i,p},1});
      }
      v[i][p].push_back({{i,0},0});
    }
  }
  for(int i = 0;i < m;i++){
    int q,p;
    cin >>q>>p;
    pos[i] = q;
    if(p <= buck){
      v[q][0].push_back({{q,p},0});
    }else{
      int cnt = 1;
      for(int j = q - p;j >= 0;j -= p){
        v[q][0].push_back({{j,0},cnt});
        cnt++;
      }
      cnt = 1;
      for(int j = q + p;j < n;j += p){
        v[q][0].push_back({{j,0},cnt});
        cnt++;
      }
    }
  }
  for(int i = 0;i < n;i++){
    for(int p = 0;p <= buck;p++){
      dist[i][p] = 1e9;
    }
  }
  dist[pos[0]][0] = 0;
  priority_queue<pair<node,int>>q;
  q.push({{pos[0],0},0});
  while(q.size()){
    auto u = q.top();
    // cout<<u.F.q<<' '<<u.F.p<<' '<<u.S<<'\n';
    q.pop();
    if(dist[u.F.q][u.F.p] < u.S) continue;
    for(auto x : v[u.F.q][u.F.p]){
      if(dist[x.F.q][x.F.p] > u.S + x.S){
        dist[x.F.q][x.F.p] = u.S + x.S;
        q.push({{x.F},dist[x.F.q][x.F.p]});
      }
    }
  }
  cout<<(dist[pos[1]][0] == 1e9 ? -1 : dist[pos[1]][0]);
}

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