제출 #1242902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242902		Hamed_Ghaffari	Passport (JOI23_passport)	C++20	16 / 100	3 ms	584 KiB

passport

#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;
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46