Submission #888805

#	Time	Username	Problem	Language	Result	Execution time	Memory
888805		vjudge1	Passport (JOI23_passport)	C++17	22 / 100	2065 ms	49500 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> L(n), R(n);
    for ( int i = 0; i < n; i++ ){
        cin >> L[i] >> R[i];
        --L[i], --R[i];
    }
    int qq; cin >> qq;
    while ( qq-- ){
        int s; cin >> s;
        --s;
        if ( !s ){
            int ans = 0, lst = -1;
            bool flag = true;
            priority_queue <int> q;
            q.push(R[s]);
            for ( int i = 1; i < n; i++ ){
                if ( lst < i ){
                    if ( q.empty() || q.top() < i ){
                        flag = false;
                        break;
                    }
                    lst = q.top();
                    q.pop(); ++ans;
                } q.push(R[i]);
            }
            cout << (flag ? ans : -1) << ln;
            continue;
        }
        const int inf = 1e15;
        vector <vector<int>> dp(n, vector <int> (n, inf));
        dp[L[s]][R[s]] = 1;
        queue <ar<int,2>> q;
        q.push({L[s], R[s]});
        while ( !q.empty() ){
            auto [u, v] = q.front();
            q.pop();
            for ( int j = u; j <= v; j++ ){
                int x = min(u, L[j]), y = max(v, R[j]);
                if ( chmin(dp[x][y], dp[u][v] + 1) ){
                    q.push({x, y});
                }
            }
        }
        int ans = dp[0][n - 1];
        if ( ans == inf ){
            ans = -1;
        }
        cout << ans << ln;
    }

    cout << '\n';
}

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