Submission #1150475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150475		Persia	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	529 ms	25532 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define bit(i, x) (x >> i & 1)
#define ll long long
#define sz(x) (int)x.size()

const int N = 30005;
const int mod = 998244353;

const int S = 173;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

int n, m;
pair<int, int> a[N];
int d[N][S + 5];
vector<int> adj[N];
pair<int, int> s, t;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q;
int res, INF;
bool vst[N];

bool minimize(int &x, int y) {
    if(x <= y) return 0;
    x = y;
    return 1;
}

signed main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(d, 0x3f, sizeof d);
    INF = d[0][0];

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
        adj[a[i].first].push_back(a[i].second);

        if(i == 0) s = {a[i].first, 0};
        else if(i == 1) t = {a[i].first, 0};
    }

    d[s.first][0] = 0;
    q.push({0, s.first, 0});
    while(!q.empty()) {
        auto [val, u, k] = q.top();
        q.pop();
        assert(k <= S);
        if(val > d[u][k]) continue;
        // cout << u << " " << k << "\n";

        if(k == 0) {
            for(int k2 : adj[u]) {
                if(k2 <= S) {
                    if(minimize(d[u][k2], val)) q.push({val, u, k2});
                }
                else {
                    for(int v = u % k2; v <= n - 1; v += k2) {
                        int dist = abs(u - v);
                        assert(dist % k2 == 0);
                        dist /= k2;
                        if(minimize(d[v][0], val + dist)) q.push({d[v][0], v, 0});
                    }
                }
            }
            continue;
        }
        if(k <= S) {
            if(u - k >= 0) {
                if(minimize(d[u - k][0], val + 1)) q.push({d[u - k][0], u - k, 0});
                if(minimize(d[u - k][k], val + 1)) q.push({d[u - k][k], u - k, k});
            }
            if(u + k <= n - 1) {
                if(minimize(d[u + k][0], val + 1)) q.push({d[u + k][0], u + k, 0});
                if(minimize(d[u + k][k], val + 1)) q.push({d[u + k][k], u + k, k});
            }
        }
        else {
            for(int v = u % k; v <= n - 1; v += k) {
                int dist = abs(u - v);
                assert(dist % k == 0);
                dist /= k;
                if(minimize(d[v][0], val + dist)) q.push({d[v][0], v, 0});
            }
        }
    }

    res = d[t.first][0];
    if(res == INF) res = -1;
    cout << res;

    

    // cout << s.first << " " << s.second;
    // cout << "\n";
    // cout << t.first << " " << t.second;

    return 0 ^ 0;
}

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