Submission #315870

#	Time	Username	Problem	Language	Result	Execution time	Memory
315870		ewwdsgfvsd	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1093 ms	4728 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=5e4+10,LN=30,SQ=550,M=1e5+10;
const ll INF=1e15;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,m,s,t,h[N];
vector<ll> adj[N];
priority_queue<pll> q;
int main(){
    fast_io;
    cin >> n >> m;
    for(ll i=0; i<m; i++){
        ll b,p;
        cin >> b >> p;
        if(i==0) s=b;
        if(i==1) t=b;
        adj[b].push_back(p);
    }
    memset(h,63,sizeof h);
    h[s]=0;
    q.push({0,s});
    while(!q.empty()){
        ll v=q.top().S,x=-q.top().F;
        q.pop();
        if(h[v]<x) continue;
        for(ll t : adj[v]){
            for(ll u=v-t,j=1; u>=0; u-=t,j++){
                if(h[u]<=x+j) continue;
                h[u]=x+j;
                q.push({-h[u],u});
            }
            for(ll u=v+t,j=1; u<n; u+=t,j++){
                if(h[u]<=x+j) continue;
                h[u]=x+j;
                q.push({-h[u],u});
            }
        }
    }
    if(h[t]<=INF) cout << h[t] << '\n';
    else cout << -1 << '\n';
    return 0;
}

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