Submission #1086435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086435		pemguimn	Passport (JOI23_passport)	C++17	48 / 100	898 ms	398160 KiB

passport

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5e2 + 1, INF = 1e9 + 7;

vector<array<int, 3>> adj[N][N];
int n, l[N], r[N], q;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }

    for(int i = 1; i <= n; i++){
        adj[l[i]][r[i]].push_back({i, i, 1});
        int mn = INF, mx = 0;
        for(int j = i; j <= n; j++){
            mx = max(mx, r[j]), mn = min(mn, l[j]);
            if(i < j){
                adj[mn][j].push_back({i, j, 1});
                adj[i][mx].push_back({i, j, 1});
                adj[i + 1][j].push_back({i, j, 0});
                adj[i][j - 1].push_back({i, j, 0});
            }
        }
    }

    vector d(n + 1, vector<int>(n + 1, INF));
    deque<pair<int, int>> dq; dq.push_front({1, n}); d[1][n] = 0;
    while(!dq.empty()){
        auto [l, r] = dq.front(); dq.pop_front();

        for(array<int, 3> e : adj[l][r]){
            int w = e[2];
            if(d[l][r] + w < d[e[0]][e[1]]){
                d[e[0]][e[1]] = d[l][r] + w;
                if(w == 0){
                    dq.push_front({e[0], e[1]});
                } else{
                    dq.push_back({e[0], e[1]});
                }
            }
        }
    }
    cin >> q;
    while(q--){
        int x; cin >> x;
        if(d[x][x] > 1e9) cout << -1 << '\n';
        else cout << d[x][x] << '\n';
    }

    return 0;
}

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