Submission #888872

#	Time	Username	Problem	Language	Result	Execution time	Memory
888872		viwlesxq	Passport (JOI23_passport)	C++17	22 / 100	2053 ms	25024 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T> 
bool chmin(S &a, const T &b) {
    return (a > b ? (a = b) == b : false);
}
template<class S, class T> 
bool chmax(S &a, const T &b) {
    return (a < b ? (a = b) == b : false);
}
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 998244353;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int l[n], r[n];
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        l[i]--, r[i]--;
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        x--;
        if (!x) {
            int res = 0, last = -1;
            bool flag = true;
            priority_queue<int> q;
            q.push(r[x]);
            for (int i = 1; i < n; ++i) {
                if (last < i) {
                    if (q.empty() || q.top() < i) {
                        flag = false;
                        break;
                    }
                    last = q.top();
                    q.pop();
                    res++;
                }
                q.push(r[i]);
            }
            cout << (flag ? res : -1) << '\n';
        } else {
            vector<vector<int>> d(n, vector<int> (n, inf));
            queue<pair<int, int>> q;
            d[l[x]][r[x]] = 1;
            q.push({l[x], r[x]});
            while (!q.empty()) {
                auto [L, R] = q.front(); 
                q.pop();
                for (int i = L; i <= R; ++i) {
                    int new_l = min(L, l[i]), new_r = max(R, r[i]);
                    if (chmin(d[new_l][new_r], d[L][R] + 1)) {
                        q.push({new_l, new_r});
                    }
                }
            }
            cout << (d[0][n - 1] == inf ? -1 : d[0][n - 1]) << '\n';
        }
    }
}

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