oj.uz

Submission #1086571

# Submission time Handle Problem Language Result Execution time Memory
1086571 2024-09-11T04:57:03 Z daoquanglinh2007 Passport (JOI23_passport) C++17
16 / 100
 438 ms 526876 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
 
const int NM = 2500, inf = 1e9+7;
 
int ntest = 1;
int N, Q, L[NM+5], R[NM+5], bestL[NM+5][NM+5], bestR[NM+5][NM+5];
vector <pii> adj[NM+5][NM+5];
queue <pii> q;
int dist[NM+5][NM+5];
 
void solve(){
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> L[i] >> R[i];
    for (int i = 1; i <= N; i++){
        bestL[i][i] = bestR[i][i] = i;
        for (int j = i+1; j <= N; j++){
            if (mp(L[j], -R[j]) < mp(L[bestL[i][j-1]], -R[bestL[i][j-1]])) bestL[i][j] = j;
            else bestL[i][j] = bestL[i][j-1];

            if (mp(R[j], -L[j]) > mp(R[bestR[i][j-1]], -L[bestR[i][j-1]])) bestR[i][j] = j;
            else bestR[i][j] = bestR[i][j-1];
        }
        for (int j = i; j <= N; j++){
            int x = min(i, L[bestL[i][j]]), y = max(j, R[bestL[i][j]]);
            adj[x][y].push_back(mp(i, j));
            x = min(i, L[bestR[i][j]]), y = max(j, R[bestR[i][j]]);
            adj[x][y].push_back(mp(i, j));
            dist[i][j] = -1;
        }
    }
    dist[1][N] = 0;
    q.push(mp(1, N));
    while (!q.empty()){
        int l = q.front().fi, r = q.front().se; q.pop();
        for (pii p : adj[l][r]){
            if (dist[p.fi][p.se] != -1) continue;
            dist[p.fi][p.se] = dist[l][r]+1;
            q.push(mp(p.fi, p.se));
        }
    }
    cin >> Q;
    while (Q--){
        int X; cin >> X;
        cout << dist[X][X] << '\n';
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //cin >> ntest;
    while (ntest--){
        solve();
    }
 
#ifdef daoquanglinh2007
    cout << '\n';
    for (int i = 1; i <= 100; i++) cout << '=';
    cout << "\nExecution time: " << 1*(clock()) << " ms\n";
#endif
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147876 KB Output is correct
2 Correct 62 ms 147832 KB Output is correct
3 Correct 60 ms 147732 KB Output is correct
4 Runtime error 382 ms 526876 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 147716 KB Output is correct
2 Correct 64 ms 147808 KB Output is correct
3 Correct 65 ms 147808 KB Output is correct
4 Correct 67 ms 147804 KB Output is correct
5 Correct 67 ms 147736 KB Output is correct
6 Correct 66 ms 147668 KB Output is correct
7 Correct 72 ms 147808 KB Output is correct
8 Correct 67 ms 147848 KB Output is correct
9 Correct 67 ms 147864 KB Output is correct
10 Correct 67 ms 147808 KB Output is correct
11 Correct 76 ms 152792 KB Output is correct
12 Correct 72 ms 153240 KB Output is correct
13 Correct 72 ms 152928 KB Output is correct
14 Correct 70 ms 152796 KB Output is correct
15 Correct 72 ms 153696 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 147716 KB Output is correct
2 Correct 64 ms 147808 KB Output is correct
3 Correct 65 ms 147808 KB Output is correct
4 Correct 67 ms 147804 KB Output is correct
5 Correct 67 ms 147736 KB Output is correct
6 Correct 66 ms 147668 KB Output is correct
7 Correct 72 ms 147808 KB Output is correct
8 Correct 67 ms 147848 KB Output is correct
9 Correct 67 ms 147864 KB Output is correct
10 Correct 67 ms 147808 KB Output is correct
11 Correct 76 ms 152792 KB Output is correct
12 Correct 72 ms 153240 KB Output is correct
13 Correct 72 ms 152928 KB Output is correct
14 Correct 70 ms 152796 KB Output is correct
15 Correct 72 ms 153696 KB Output is correct
16 Correct 202 ms 267748 KB Output is correct
17 Incorrect 438 ms 298492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 147716 KB Output is correct
2 Correct 64 ms 147808 KB Output is correct
3 Correct 65 ms 147808 KB Output is correct
4 Correct 67 ms 147804 KB Output is correct
5 Correct 67 ms 147736 KB Output is correct
6 Correct 66 ms 147668 KB Output is correct
7 Correct 72 ms 147808 KB Output is correct
8 Correct 67 ms 147848 KB Output is correct
9 Correct 67 ms 147864 KB Output is correct
10 Correct 67 ms 147808 KB Output is correct
11 Correct 76 ms 152792 KB Output is correct
12 Correct 72 ms 153240 KB Output is correct
13 Correct 72 ms 152928 KB Output is correct
14 Correct 70 ms 152796 KB Output is correct
15 Correct 72 ms 153696 KB Output is correct
16 Correct 202 ms 267748 KB Output is correct
17 Incorrect 438 ms 298492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147876 KB Output is correct
2 Correct 62 ms 147832 KB Output is correct
3 Correct 60 ms 147732 KB Output is correct
4 Runtime error 382 ms 526876 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -