Submission #1094482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094482		ShaShi	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	94 ms	74736 KiB

skyscraper

#include <bits/stdc++.h>
 
//#define int long long 
 
 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 #pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e9 + 7;
 
 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, l, r, mid;
int dis[MAXN], ind[MAXN], val[MAXN];
vector<int> arr[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
map<int, bool> cnt[MAXN];

 
inline void relax(int v, int u) {
    if (val[v] == val[u]) return;
    if (dis[u] <= dis[v]+abs(ind[u]-ind[v])/val[v]) return;
 
    dis[u] = dis[v] + abs(ind[u]-ind[v])/val[v];
 
    pq.push({dis[u], u});
}
 
 
int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif
 
 
    cin >> n >> m;
 
    for (int i=1; i<=m; i++) {
        cin >> ind[i] >> val[i]; ind[i]++;
        
        if (i == 2) val[i] = MAXN;

        if (!cnt[ind[i]][val[i]]) arr[ind[i]].pb(i), cnt[ind[i]][val[i]] = 1;
    }
 
    fill_n(dis, m+7, INF); 
 
    dis[1] = 0; pq.push({0, 1});
 
    while (pq.size()) {
        auto cur = pq.top(); pq.pop();
 
        if (dis[cur.S] != cur.F) continue;
 
        // cout << "! " << cur.S << " " << cur.F << endl;
 
        v = cur.S;
 
        if (v == 2) kill(dis[v]);
 
        for (int i=ind[v]; i<=n; i+=val[v]) for (auto cur:arr[i]) relax(v, cur);
        for (int i=ind[v]; i>0; i-=val[v]) for (auto cur:arr[i]) relax(v, cur);
    }
 
    kill(-1);
 
    
    return 0;
}

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