Submission #108288

#	Time	Username	Problem	Language	Result	Execution time	Memory
108288		golub	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	267 ms	66420 KiB

skyscraper

// #define TASK "sweets"

#pragma GCC optimize("Ofast")
// #pragma GCC target("sse4.2,avx2")
// #pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unroll-all-loops")

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>

// using namespace __gnu_cxx;`
// using namespace __gnu_pbds;
using namespace std;

// template<class K>
// using ordered_set = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

// template<class K, class T>
// using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 rnd((int)chrono::high_resolution_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
#define len(x) (long long)x.size()
// #define int long long

typedef long long ll;
typedef long double ld;

const long long INF = (int)numeric_limits<int>::max() >> 1;
const long long MAXN = (long long)1e5 + 10;
const long long MOD = (long long)1e9 + 7;
const long double EPS = (long double)1e-12;

// char _buf_[(int)6e6];
// size_t _p_ = 0;

// inline void *operator new(size_t _n_) {
//    _p_ += _n_;
//    return _buf_ + _p_ - _n_;
// }
// inline void operator delete(void*) {};

ll power(ll x, ll n, ll mod = 1e9 + 7) {
    if (n == 0) return 1ll;
    if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
    ll tmp = power(x, n >> 1ll, mod);
    return (tmp * tmp) % mod;
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd (b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

template<typename A, typename B>
bool cmax(A &a, const B &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<typename A, typename B>
bool cmin(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

vector<int> b, p;

vector<vector<pii>> g;
int n, s, f, m;

int solve() {
    vector<int> dist(n, INF), used(n, 0);
    dist[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> cur;
    cur.push({0, s});

    while (!cur.empty()) {
        pii v = cur.top();
        cur.pop();
        if (used[v.S]) continue;
        used[v.S] = 1;
        for (auto u: g[v.S]) {
            int cost = u.S;
            if (cmin(dist[u.F], dist[v.S] + cost))
                cur.push({dist[u.F], u.F});
        }
    }
    return dist[f];
}

signed main() {
#ifndef LOCAL
    #ifdef TASK
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif
#endif
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // == SOLUTION == //
    cin >> n >> m;
    b.resize(m); p.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
    }
    s = b[0]; f = b[1];

    set<int> Power[n];
    for (int i = 0; i < m; i++) {
        Power[b[i]].insert(p[i]);
    }

    vector<pii> players;
    for (int i = 0; i < m; i++) {
        players.pb({b[i], p[i]});
    }
    sort(all(players));

    players.resize(unique(all(players)) - players.begin());
    p.clear(); b.clear();
    p.resize(len(players)); b.resize(len(players));
    for (int i = 0; i < len(players); i++) {
        b[i] = players[i].F;
        p[i] = players[i].S;
    }
    m = len(players);
    
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int x = b[i];
        int dx = p[i];
        
        int cnt = 0;
        int cur = x + dx;
        while (cur < n) {
            cnt++;
            g[x].pb({cur, cnt});
            if (Power[cur].find(dx) != Power[cur].end()) break;
            cur += dx;
        }
        cnt = 0;
        cur = x - dx;
        while(cur >= 0) {
            cnt++;
            g[x].pb({cur, cnt});
            if (Power[cur].find(dx) != Power[cur].end()) break;
            cur -= dx;
        }
    }

    int ans = solve();
    if (ans == INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << ans << "\n";

} 

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