Submission #874652

#	Time	Username	Problem	Language	Result	Execution time	Memory
874652		Iliya_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	764 ms	4300 KiB

skyscraper

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define all(x)      x.begin(),x.end()
#define pb          push_back
using namespace std;
typedef long long ll; 

#pragma GCC target("avx2")
const int N = 3e4+7, inf = 1e9;
int a[N], p[N], d[N], mark[N];
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; 
int v,u;

void dij(int n){
     fill(d,d+n,inf);
     d[a[0]] = 0; 
     q.push({0,a[0]}); 
     while(q.size()){
          v = q.top().S;
          q.pop();
          if (v == a[1]) return;
          if (mark[v]) continue; 
          mark[v] = 1;
          for (int p : g[v]){
               for(int i=1; v+i*p<n; i++){
                    u = v + i * p;
                    if (d[u] > d[v] + i){
                         d[u] = d[v] + i;
                         q.push({d[u],u}); 
                    }
               }
               for(int i=1; v-i*p>=0; i++){
                    u = v - i*p;
                    if (d[u] > d[v] + i){
                         d[u] = d[v] + i;
                         q.push({d[u],u});
                    }
               }
          }
     }
}

int32_t main(){
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     
     int n,m; cin >> n >> m; 
     for(int i=0; i<m; i++){
          cin >> a[i] >> p[i]; 
          g[a[i]].pb(p[i]);
     }
     dij(n); 
     cout << (d[a[1]] == inf ? -1 : d[a[1]]) << endl; 

     return 0;
}

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