Submission #1176067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176067		VMaksimoski008	Passport (JOI23_passport)	C++17	40 / 100	2105 ms	1114112 KiB

passport

#include <bits/stdc++.h>
#define ar array
using namespace std;

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

    int n; cin >> n;
    vector<int> L(n+1), R(n+1);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];

    vector<ar<int, 3> > G[n+1][n+1];
    int dp[n+1][n+1];

    for(int i=1; i<=n; i++) G[i][i].push_back({ L[i], R[i], 1 });
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            G[i][j].push_back({ i+1, j, 0 });
            G[i][j].push_back({ i, j-1, 0 });
        } 
    }

    for(int i=1; i<=n; i++) {
        int mn = 1e9, mx = 0;
        for(int j=i; j<=n; j++) {
            mn = min(mn, L[j]);
            mx = max(mx, R[j]);
            G[i][j].push_back({ mn, j, 1 });
            G[i][j].push_back({ i, mx, 1 });
        }
    }

    int q; cin >> q;
    priority_queue<ar<int, 3>, vector<ar<int, 3> >, greater<> > pq;
    while(q--) {
        int x; cin >> x;
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++) dp[i][j] = 1e9;

        pq.push({ dp[x][x] = 0, x, x });
        while(!pq.empty()) {
            auto [d, l, r] = pq.top(); pq.pop();
            if(dp[l][r] != d) continue;

            for(auto [l2, r2, w] : G[l][r])
                if(dp[l2][r2] > d + w) pq.push({ dp[l2][r2] = d + w, l2, r2 });
        }

        cout << (dp[1][n] == 1e9 ? -1 : dp[1][n]) << '\n';
    }
}

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