Submission #1242902

#TimeUsernameProblemLanguageResultExecution timeMemory
1242902Hamed_GhaffariPassport (JOI23_passport)C++20
16 / 100
3 ms584 KiB
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

const int MXN = 303;

int n, L[MXN], R[MXN], q, xq[MXN], dis[MXN][MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    assert(n<=300);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];
    cin >> q;
    assert(q==1);
    for(int i=1; i<=q; i++) cin >> xq[i];
    memset(dis, -1, sizeof(dis));
    queue<pii> qu;
    dis[xq[1]][xq[1]] = 0;
    qu.push({xq[1], xq[1]});
    while(!qu.empty()) {
        auto [l, r] = qu.front();
        qu.pop();
        pii mn = {1e9, 1e9}, mx = {-1e9, -1e9};
        for(int i=l; i<=r; i++) {
            mn = min(mn, pii(min(l, L[i]), -max(r, R[i])));
            mx = max(mx, pii(max(r, R[i]), -min(l, L[i])));
        }
        int l2 = mn.first, r2 = -mn.second;
        if(dis[l2][r2]==-1) {
            dis[l2][r2] = dis[l][r]+1;
            qu.push({l2, r2});
        }
        l2 = -mx.second, r2 = mx.first;
        if(dis[l2][r2]==-1) {
            dis[l2][r2] = dis[l][r]+1;
            qu.push({l2, r2});
        }
    }
    cout << dis[1][n] << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...