oj.uz

답안 #1086435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086435 2024-09-10T15:38:18 Z pemguimn Passport (JOI23_passport) C++17
48 / 100
 898 ms 398160 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5e2 + 1, INF = 1e9 + 7;

vector<array<int, 3>> adj[N][N];
int n, l[N], r[N], q;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }

    for(int i = 1; i <= n; i++){
        adj[l[i]][r[i]].push_back({i, i, 1});
        int mn = INF, mx = 0;
        for(int j = i; j <= n; j++){
            mx = max(mx, r[j]), mn = min(mn, l[j]);
            if(i < j){
                adj[mn][j].push_back({i, j, 1});
                adj[i][mx].push_back({i, j, 1});
                adj[i + 1][j].push_back({i, j, 0});
                adj[i][j - 1].push_back({i, j, 0});
            }
        }
    }

    vector d(n + 1, vector<int>(n + 1, INF));
    deque<pair<int, int>> dq; dq.push_front({1, n}); d[1][n] = 0;
    while(!dq.empty()){
        auto [l, r] = dq.front(); dq.pop_front();

        for(array<int, 3> e : adj[l][r]){
            int w = e[2];
            if(d[l][r] + w < d[e[0]][e[1]]){
                d[e[0]][e[1]] = d[l][r] + w;
                if(w == 0){
                    dq.push_front({e[0], e[1]});
                } else{
                    dq.push_back({e[0], e[1]});
                }
            }
        }
    }
    cin >> q;
    while(q--){
        int x; cin >> x;
        if(d[x][x] > 1e9) cout << -1 << '\n';
        else cout << d[x][x] << '\n';
    }

    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 147228 KB Output is correct
2 Correct 59 ms 147280 KB Output is correct
3 Correct 58 ms 147280 KB Output is correct
4 Runtime error 268 ms 384588 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 147296 KB Output is correct
2 Correct 58 ms 147296 KB Output is correct
3 Correct 60 ms 147148 KB Output is correct
4 Correct 63 ms 147340 KB Output is correct
5 Correct 59 ms 147296 KB Output is correct
6 Correct 63 ms 147216 KB Output is correct
7 Correct 60 ms 147332 KB Output is correct
8 Correct 63 ms 147288 KB Output is correct
9 Correct 60 ms 147084 KB Output is correct
10 Correct 62 ms 147332 KB Output is correct
11 Correct 69 ms 150352 KB Output is correct
12 Correct 67 ms 150608 KB Output is correct
13 Correct 72 ms 150868 KB Output is correct
14 Correct 75 ms 150580 KB Output is correct
15 Correct 68 ms 150932 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 147296 KB Output is correct
2 Correct 58 ms 147296 KB Output is correct
3 Correct 60 ms 147148 KB Output is correct
4 Correct 63 ms 147340 KB Output is correct
5 Correct 59 ms 147296 KB Output is correct
6 Correct 63 ms 147216 KB Output is correct
7 Correct 60 ms 147332 KB Output is correct
8 Correct 63 ms 147288 KB Output is correct
9 Correct 60 ms 147084 KB Output is correct
10 Correct 62 ms 147332 KB Output is correct
11 Correct 69 ms 150352 KB Output is correct
12 Correct 67 ms 150608 KB Output is correct
13 Correct 72 ms 150868 KB Output is correct
14 Correct 75 ms 150580 KB Output is correct
15 Correct 68 ms 150932 KB Output is correct
16 Correct 535 ms 356260 KB Output is correct
17 Correct 796 ms 390708 KB Output is correct
18 Correct 572 ms 381352 KB Output is correct
19 Correct 512 ms 374244 KB Output is correct
20 Correct 573 ms 367712 KB Output is correct
21 Correct 524 ms 398160 KB Output is correct
22 Correct 460 ms 381628 KB Output is correct
23 Correct 639 ms 384352 KB Output is correct
24 Correct 520 ms 384224 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 147296 KB Output is correct
2 Correct 58 ms 147296 KB Output is correct
3 Correct 60 ms 147148 KB Output is correct
4 Correct 63 ms 147340 KB Output is correct
5 Correct 59 ms 147296 KB Output is correct
6 Correct 63 ms 147216 KB Output is correct
7 Correct 60 ms 147332 KB Output is correct
8 Correct 63 ms 147288 KB Output is correct
9 Correct 60 ms 147084 KB Output is correct
10 Correct 62 ms 147332 KB Output is correct
11 Correct 69 ms 150352 KB Output is correct
12 Correct 67 ms 150608 KB Output is correct
13 Correct 72 ms 150868 KB Output is correct
14 Correct 75 ms 150580 KB Output is correct
15 Correct 68 ms 150932 KB Output is correct
16 Correct 535 ms 356260 KB Output is correct
17 Correct 796 ms 390708 KB Output is correct
18 Correct 572 ms 381352 KB Output is correct
19 Correct 512 ms 374244 KB Output is correct
20 Correct 573 ms 367712 KB Output is correct
21 Correct 524 ms 398160 KB Output is correct
22 Correct 460 ms 381628 KB Output is correct
23 Correct 639 ms 384352 KB Output is correct
24 Correct 520 ms 384224 KB Output is correct
25 Correct 57 ms 147284 KB Output is correct
26 Correct 59 ms 147284 KB Output is correct
27 Correct 527 ms 372228 KB Output is correct
28 Correct 898 ms 394108 KB Output is correct
29 Correct 597 ms 367696 KB Output is correct
30 Correct 540 ms 398144 KB Output is correct
31 Correct 502 ms 373000 KB Output is correct

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 147228 KB Output is correct
2 Correct 59 ms 147280 KB Output is correct
3 Correct 58 ms 147280 KB Output is correct
4 Runtime error 268 ms 384588 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -