Submission #1275881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275881		itsKiaRash	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	621 ms	5556 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds; // find_by_order   order_of_key
// template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize ("Ofast")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #define int ll
#define FAST_IO (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define testc int ttt;cin>>ttt;while(ttt--)
#define alll(x)	(x).begin(),(x).end()
#define pqi priority_queue<pii, vector<pii>, greater<pii>>
#define endl '\n'
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define ff first
#define ss second
#define bg begin
#define rbg rbegin
#define sz size()
#define mset(x,y) memset(x,y,sizeof(x))
#define clr clear()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define vci vector<int>
#define sti set<int>
#define nl cout<<'\n'
#define upb upper_bound
#define lrb lower_bound
//ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
const ll inf = 1e18 + 18;
const int maxn = 3e4 + 7, mod = 1e9 + 7; //998244353
int n, m;
ll p[maxn], b[maxn], val[maxn];
vci adj[maxn];
// void dij(int a){
//     fill(val, val + n + 1, inf);
//     val[a] = 0;
//     pqi pq; pq.push({0, a});
//     while(pq.sz){
//         auto[ww, u] = pq.top(); pq.pop();
//         if(ww > val[u]) continue;
//         for(auto[w, v] : adj[u]){
//             if(val[u] + w < val[v]){
//                 val[v] = val[u] + w;
//                 pq.push({val[v], v});
//             }
//         }
//     }
// }
void deltek(){
    for(int i = 0 ; i < n ; i ++){
      sort(alll(adj[i]));
      adj[i].erase(unique(alll(adj[i])), adj[i].end());
    }
}

void dij(int a){
    pqi pq;
    fill(val, val + n + 1, inf); val[a] = 0;
    pq.push({0, a});
    while(pq.sz){
        auto [ww, x] = pq.top(); pq.pop();
        if(ww > val[x]) continue;
        for(int item : adj[x]){
            int dst = 0;
            for(int i = x + item ; i < n ; i += item){ dst ++;
                if(val[x] + dst < val[i]){
                  val[i] = val[x] + dst;
                  pq.push({val[i], i});
                }
            }
            dst = 0;
            for(int i = x - item ; i >= 0 ; i -= item){ dst ++;
                if(val[x] + dst < val[i]){
                    val[i] = val[x] + dst;
                    pq.push({val[i], i});
                }
            }
        }
    }
}
int32_t main() {
    FAST_IO
    cin >> n >> m;
    for(int i = 0 ; i < m ; i ++){
      cin >> b[i] >> p[i]; adj[b[i]].pb(p[i]);
    } deltek();
    dij(b[0]);
    if(val[b[1]] >= inf) val[b[1]] = -1;
    cout << val[b[1]] << endl;

    return 0; 
}

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