제출 #1149767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149767		Persia	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	11 ms	16224 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 = 2e5 + 5;
const int mod = 998244353;

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> S, T;
vector<vector<int>> adj;
vector<vector<int>> d;
deque<pair<int, int>> q;

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

    cin >> n >> m;
    adj.assign(n + 3, vector<int>(0));
    for(int i = 1; i <= m; i++) {
        int b, p; cin >> b >> p;
        adj[b].push_back(p);
        if(i == 1) {
            S = {b, p};
        }
        else if(i == 2) {
            T = {b, p};
        }

    }

    if(S.first == T.first) {
        cout << 0;
        return 0;
    }

    if(S.second > n) {
        cout << -1;
        return 0;
    }

    d.assign(n + 3, vector<int>(n + 3, 1e9));
    d[S.first][S.second] = 0;
    q.push_back(S);
    while(!q.empty()) {
        auto [u, k] = q.front();
        q.pop_front();
        // cout << u << " ";
        for(int k2 : adj[u]) {
            if(k2 <= n && d[u][k2] > d[u][k]) {
                d[u][k2] = d[u][k];
                q.push_front({u, k2});
            }
        }
        if(u + k <= n - 1 && d[u + k][k] > d[u][k] + 1) {
            d[u + k][k] = d[u][k] + 1;
            q.push_back({u + k, k});
        }
        if(u - k >= 0 && d[u - k][k] > d[u][k] + 1) {
            d[u - k][k] = d[u][k] + 1;
            q.push_back({u - k, k});
        }
    }

    int res = 1e9;
    for(int i = 0; i <= n; i++) res = min(res, d[T.first][i]);
    if(res == 1e9) res = -1;
    cout << res;

    // for(int i : adj[1]) cout << i << " ";

    return 0 ^ 0;
}

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