제출 #1165828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165828		antonn	밀림 점프 (APIO21_jumps)	C++20	0 / 100	11 ms	1708 KiB

jumps

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e3 + 7;
const int L = 20;

int l[N], r[N], to[N], dist[N][N], vis[N];
vector<pi> g[N];

void add_edge(int a, int b, int c) {
    g[a].push_back({b, c});
}

void init(int n, vector<int> h) {
    vector<int> stk;
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && h[i - 1] > h[stk.back() - 1]) stk.pop_back();
        if (!stk.empty()) r[i] = stk.back();
        if (stk.empty()) r[i] = n + 1; 
        stk.push_back(i);
    }
    stk.clear();
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && h[i - 1] > h[stk.back() - 1]) stk.pop_back();
        if (!stk.empty()) l[i] = stk.back();
        if (stk.empty()) l[i] = 0; 
        stk.push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        if (r[i] == n + 1) {
            to[i] = l[i];
            continue;
        }
        if (l[i] == 0) {
            to[i] = r[i];
            continue;
        }
        if (r[i] < r[l[i]]) {
            to[i] = l[i];
        } else {
            to[i] = r[i];
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (r[i] != n + 1) add_edge(i, r[i], 1);
        int j = i, cost = 0;
        while (to[j] < j) j = to[j], ++cost;
        if (j != i) add_edge(i, to[j], cost + 1);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) dist[i][j] = 1e9, vis[i] = 0;
        priority_queue<pi> pq;
        dist[i][i] = 0;
        pq.push({0, i});
        while (!pq.empty()) {
            int u = pq.top().S;
            pq.pop();
            if (vis[u] == 1) continue;
            vis[u] = 1;
            for (auto [v, c] : g[u]) {
                if (dist[i][u] + c < dist[i][v]) {
                    dist[i][v] = dist[i][u] + c;
                    pq.push({-dist[i][v], v});
                } 
            }
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    ++a, ++b, ++c, ++d;
    int ans = 1e9;
    for (int i = a; i <= b; ++i) {
        for (int j = c; j <= d; ++j) {
            ckmin(ans, dist[i][j]);
        }
    }
    if (ans == 1e9) ans = -1;
    return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19