oj.uz

Submission #888748

# Submission time Handle Problem Language Result Execution time Memory
888748 2023-12-18T07:16:43 Z vjudge1 Passport (JOI23_passport) C++17
0 / 100
 32 ms 50524 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24780 KB Output is correct
2 Correct 11 ms 24792 KB Output is correct
3 Correct 12 ms 24920 KB Output is correct
4 Runtime error 32 ms 50524 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 24880 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 13 ms 24920 KB Output is correct
7 Incorrect 12 ms 24924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 24880 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 13 ms 24920 KB Output is correct
7 Incorrect 12 ms 24924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 24880 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 13 ms 24920 KB Output is correct
7 Incorrect 12 ms 24924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24780 KB Output is correct
2 Correct 11 ms 24792 KB Output is correct
3 Correct 12 ms 24920 KB Output is correct
4 Runtime error 32 ms 50524 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -