Submission #793855

#	Time	Username	Problem	Language	Result	Execution time	Memory
793855		vjudge1	Passport (JOI23_passport)	C++17	46 / 100	1217 ms	25040 KiB

passport

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 200200;

pair < int, int > pass[N];
int n, q, x;
int dp[2525][2525];
bool in_que[2525][2525];

void solve_subtask_1() {
    int ans = 1, pr_r = 1, cr_r = pass[1].second, nw_r = 1;
    for(; cr_r < n;) {
        nw_r = cr_r;
        for(int r = pr_r + 1; r <= cr_r; ++ r) {
            if(pass[r].second > nw_r) {
                nw_r = pass[r].second;
            }
        }
        if(nw_r == cr_r) {
            cout << "-1";
            return;
        }
        ++ ans;
        pr_r = cr_r;
        cr_r = nw_r;
    }
    cout << ans << '\n';
}

void recur(int l, int r) {
    for(int i = l; i <= r; ++ i) {
        auto &[nl, nr] = pass[i];
        if(nl < l && dp[nl][max(r, nr)] > dp[l][r] + 1) {
            dp[nl][max(r, nr)] = dp[l][r] + 1;
            recur(nl, max(r, nr));
        }
        if(r < nr && dp[min(l, nl)][nr] > dp[l][r] + 1) {
            dp[min(l, nl)][nr] = dp[l][r] + 1;
            recur(min(l, nl), nr);
        }
    }
}

void solve_subtask_2_3() {
    for(int i = 1; i <= n; ++ i) {
        for(int j = i; j <= n; ++ j) {
            dp[i][j] = N;
        }
    }
    dp[pass[x].first][pass[x].second] = 1;
    queue < pair < int, int > > q;
    q.push({pass[x].first, pass[x].second});
    for(; !q.empty();) {
        auto &[l, r] = q.front();
        q.pop();
        in_que[l][r] = false;
        for(int i = l; i <= r; ++ i) {
            auto &[nl, nr] = pass[i];
            if(nl < l && dp[nl][max(r, nr)] > dp[l][r] + 1) {
                dp[nl][max(r, nr)] = dp[l][r] + 1;
                if(!in_que[nl][max(r, nr)]) {
                    in_que[nl][max(r, nr)] = true;
                    q.push({nl, max(r, nr)});
                }
            }
            if(r < nr && dp[min(l, nl)][nr] > dp[l][r] + 1) {
                dp[min(l, nl)][nr] = dp[l][r] + 1;
                if(!in_que[min(l, nl)][nr]) {
                    in_que[min(l, nl)][nr] = true;
                    q.push({min(l, nl), nr});
                }
            }
        }
    }
    cout << (dp[1][n] == N ? -1 : dp[1][n]);
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        cin >> pass[i].first >> pass[i].second;
    } 
    cin >> q >> x;
    if(q == 1 && x == 1) {
        solve_subtask_1();
        return 0;
    } 
    if(q == 1) {
        solve_subtask_2_3();
        return 0;
    }
}

Compilation message (stderr)

passport.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main() {
      | ^~~~

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