Submission #888748

#	Time	Username	Problem	Language	Result	Execution time	Memory
888748		vjudge1	Passport (JOI23_passport)	C++17	0 / 100	32 ms	50524 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T> 
bool chmin(S &a, const T &b) {
    return (a > b ? (a = b) == b : false);
}
template<class S, class T> 
bool chmax(S &a, const T &b) {
    return (a < b ? (a = b) == b : false);
}
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 998244353;
const int N = 2500;

int l[N], r[N];
vector<vector<int>> d(N, vector<int> (N, inf));

void bfs(int init) {
    deque<pair<int, int>> q;
    d[init][init] = 1;
    q.push_back({init, init});
    while (!q.empty()) {
        int v = q.front().first, k = q.front().second;
        q.pop_front();
        for (int to = l[k]; to <= r[k]; ++to) {
            if (chmin(d[to][k], d[v][k])) {
                q.push_front({to, k});
            }
        }
        if (chmin(d[v][v], d[v][k] + 1)) {
            q.push_back({v, v});
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        l[i]--, r[i]--;
    }
    int q, x;
    cin >> q >> x;
    bfs(--x);
    int res1 = inf, resn = inf;
    for (int i = 0; i < n; ++i) {
        chmin(res1, d[0][i]);
        chmin(resn, d[n - 1][i]);
    }
    int res = max(res1, resn);
    cout << (res == inf ? -1 : res);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46