Submission #1275802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275802		nariman_mt87	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1096 ms	4284 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define lli long long int
#define pii pair<lli,lli>
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define se  second
#define fi first
#define nn '\n'
#define txt freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define T int T;cin>>T;while(T--)
#define ashar(x) fixed<<setprecision(x)
#define migmig ios_base::sync_with_stdio(0);cin.tie(0);
const int maxn= 1e6 + 1, mod = 1e6 + 3;
lli pwm(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pwm(a * a , b / 2) : pwm(a * a, b / 2))); }
lli pw(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pw(a * a % mod, b / 2) % mod : pw(a * a % mod, b / 2) % mod)); }//a*pw(b,mod-2) == (a/b)%mod
lli n, m, k;
lli h[maxn], b[maxn];
vector<lli> e[maxn];
bool vis[maxn];
void dij(lli s){
    h[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while(!q.empty()){
        lli v = q.top().se, w = q.top().fi;
        q.pop();
        if(vis[v]) continue;
        vis[v] = 1;
        for(auto x : e[v]){
            lli l = 1;
            for(int i = v; i + x < n; i += x){
                if(w + l < h[i + x]){
                    h[i + x] = w + l;
                    q.push({h[i + x], i + x});
                }
                l++;
            }
            l = 1;
            for(int i = v; i - x >= 0; i -= x){
                if(w + l < h[i - x]){
                    h[i - x] = w + l;
                    q.push({h[i - x], i - x});
                }
                l++;
            }
        }
    }
}
int main(){
    migmig;
    cin >> n >> m;
    lli x, y;
    for(int i = 0; i < m; i++){
        cin >> b[i] >> y;
        e[b[i]].pb(y);
    }
    fill(h, h + n + 1, 1e9);
    dij(b[0]);
    //for(int i = 0; i < n; i ++) cerr << h[i] << " ";
    cout << (h[b[1]] == 1e9 ? -1 : h[b[1]]) << nn;
}

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