oj.uz

답안 #888751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888751 2023-12-18T07:18:31 Z vjudge1 Passport (JOI23_passport) C++17
0 / 100
 34 ms 50292 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]--;
    }
    if (n <= 2500) {
        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);
    } else {
        int q;
        cin >> q;
        while (q--) {
            int x;
            cin >> x;
            cout << 1 << '\n';
        }
    }
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24920 KB Output is correct
2 Correct 13 ms 24924 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Runtime error 34 ms 50292 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 25032 KB Output is correct
3 Correct 12 ms 24920 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 12 ms 24920 KB Output is correct
6 Correct 12 ms 24924 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 25032 KB Output is correct
3 Correct 12 ms 24920 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 12 ms 24920 KB Output is correct
6 Correct 12 ms 24924 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 12 ms 25032 KB Output is correct
3 Correct 12 ms 24920 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 12 ms 24920 KB Output is correct
6 Correct 12 ms 24924 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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24920 KB Output is correct
2 Correct 13 ms 24924 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Runtime error 34 ms 50292 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -