oj.uz

Submission #793858

# Submission time Handle Problem Language Result Execution time Memory
793858 2023-07-26T07:34:47 Z vjudge1 Passport (JOI23_passport) C++17
46 / 100
 2000 ms 24904 KB 
#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]) << '\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;
    } 
    for(int i = 1; i <= q; ++ i) {
        solve_subtask_2_3();
        if(i < q) {
            cin >> x;
        }
    }
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 27 ms 1828 KB Output is correct
5 Correct 24 ms 1732 KB Output is correct
6 Correct 24 ms 1812 KB Output is correct
7 Correct 20 ms 1788 KB Output is correct
8 Correct 16 ms 1492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 1388 ms 23512 KB Output is correct
17 Correct 659 ms 24192 KB Output is correct
18 Correct 21 ms 23508 KB Output is correct
19 Correct 30 ms 22788 KB Output is correct
20 Correct 1116 ms 24904 KB Output is correct
21 Correct 492 ms 23788 KB Output is correct
22 Correct 8 ms 20564 KB Output is correct
23 Correct 924 ms 23736 KB Output is correct
24 Correct 814 ms 23200 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 1388 ms 23512 KB Output is correct
17 Correct 659 ms 24192 KB Output is correct
18 Correct 21 ms 23508 KB Output is correct
19 Correct 30 ms 22788 KB Output is correct
20 Correct 1116 ms 24904 KB Output is correct
21 Correct 492 ms 23788 KB Output is correct
22 Correct 8 ms 20564 KB Output is correct
23 Correct 924 ms 23736 KB Output is correct
24 Correct 814 ms 23200 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Execution timed out 2058 ms 20144 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 27 ms 1828 KB Output is correct
5 Correct 24 ms 1732 KB Output is correct
6 Correct 24 ms 1812 KB Output is correct
7 Correct 20 ms 1788 KB Output is correct
8 Correct 16 ms 1492 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 2 ms 1620 KB Output is correct
20 Correct 2 ms 1748 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 3 ms 2004 KB Output is correct
24 Correct 1388 ms 23512 KB Output is correct
25 Correct 659 ms 24192 KB Output is correct
26 Correct 21 ms 23508 KB Output is correct
27 Correct 30 ms 22788 KB Output is correct
28 Correct 1116 ms 24904 KB Output is correct
29 Correct 492 ms 23788 KB Output is correct
30 Correct 8 ms 20564 KB Output is correct
31 Correct 924 ms 23736 KB Output is correct
32 Correct 814 ms 23200 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Execution timed out 2058 ms 20144 KB Time limit exceeded
36 Halted 0 ms 0 KB -