Submission #939177

#	Time	Username	Problem	Language	Result	Execution time	Memory
939177		a_l_i_r_e_z_a	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	156 ms	94340 KiB

skyscraper

// In the name of God
// Hope is last to die
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
 
const int maxn = 3e4 + 5, maxd = 1e6 + 5;
const int inf = 1e9 + 7;
int n, m, s, t, d[maxn];
vector<int> vec[maxn], asli[maxd];
vector<pii> adj[maxn];
bool mark[maxn];
 
void dij(){
    memset(d, 63, sizeof d);
    d[s] = 0;
    asli[0].pb(s);
    for(int i = 0; i < maxd; i++){
        for(auto v: asli[i]){
            for(auto [u, w]: adj[v]){
                if(d[u] > d[v] + w){
                    d[u] = d[v] + w;
                    asli[d[u]].pb(u);
                }
            }
        }
    }
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int b, p; cin >> b >> p;
        if(p < n) vec[p].pb(b);
        if(i == 0) s = b;
        if(i == 1) t = b;
    }
    for(int p = 1; p < n; p++){
        sort(all(vec[p]));
        vec[p].resize(unique(all(vec[p])) - vec[p].begin());
        for(auto u: vec[p]) mark[u] = 1;
        for(auto &i: vec[p]){
            if(!mark[i]) continue;
            for(int j = i - p; j >= 0; j -= p){
                adj[i].pb(mp(j, (i - j) / p));
                if(mark[j]) break;
            }
            for(int j = i + p; j < n; j += p){
                adj[i].pb(mp(j, (j - i) / p));
                if(mark[j]) break;
            }
        }
        for(auto u: vec[p]) mark[u] = 0;
    }
    dij();
    if(d[t] >= inf) cout << -1 << '\n';
    else cout << d[t] << '\n';
 
    return 0;
}

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