oj.uz

Submission #729339

# Submission time Handle Problem Language Result Execution time Memory
729339 2023-04-23T20:07:53 Z stevancv Passport (JOI23_passport) C++14
46 / 100
 101 ms 65264 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2500 + 2;
const int M = 2e5 + 2;
const int inf = 1e9;
int l[M], r[M], dp[N][N];
vector<int> g[N], ig[N];
void Uradi(int x) {
    queue<int> q;
    q.push(x);
    dp[x][x] = 0;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int u : g[s]) {
            if (dp[x][u] > dp[x][s] + 1) {
                q.push(u);
                dp[x][u] = dp[x][s] + 1;
            }
        }
    }
}
void Kontra(int x) {
    queue<int> q;
    q.push(x);
    dp[x][x] = 0;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int u : ig[s]) {
            if (dp[u][x] > dp[s][x] + 1) {
                q.push(u);
                dp[u][x] = dp[s][x] + 1;
            }
        }
    }
}
int st[4 * M], dpp[M];
void Add(int node, int l, int r, int x, int y) {
    smin(st[node], y);
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) Add(2 * node, l, mid, x, y);
    else Add(2 * node + 1, mid + 1, r, x, y);
}
int Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return inf;
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return min(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    int qqq, x;
    cin >> qqq >> x;
    if (x == 1) {
        for (int i = 1; i < 4 * M; i++) st[i] = inf;
        for (int i = n; i >= 1; i--) {
            if (r[i] == n) dpp[i] = 1;
            else dpp[i] = Get(1, 1, n, i, r[i]) + 1;
            smin(dpp[i], inf);
            Add(1, 1, n, i, dpp[i]);
        }
        if (dpp[1] == inf) dpp[1] = -1;
        cout << dpp[1] << en;
        return 0;
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = inf;
    for (int i = 1; i <= n; i++) {
        for (int j = l[i]; j < i; j++) {
            g[i].push_back(j);
            ig[j].push_back(i);
        }
        for (int j = i + 1; j <= r[i]; j++) {
            g[i].push_back(j);
            ig[j].push_back(i);
        }
    }
    Uradi(x);
    Kontra(1);
    Kontra(n);
    int ans = inf;
    if (x == 1 || x == n) {
        if (dp[x][n + 1 - x] == inf) dp[x][n + 1 - x] = -1;
        cout << dp[x][n + 1 - x] << en;
        return 0;
    }
    for (int i = 2; i < n; i++) smin(ans, dp[x][i] + dp[i][1] + dp[i][n] - 1);
    smin(ans, dp[x][1] + dp[1][n]);
    smin(ans, dp[x][n] + dp[n][1]);
    if (ans == inf) ans = -1;
    cout << ans << en;
    return 0;
}

Compilation message

passport.cpp: In function 'void Add(int, int, int, int, int)':
passport.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'int Get(int, int, int, int, int)':
passport.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 95 ms 8356 KB Output is correct
5 Correct 75 ms 8356 KB Output is correct
6 Correct 75 ms 8396 KB Output is correct
7 Correct 40 ms 7576 KB Output is correct
8 Correct 49 ms 7000 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3540 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 4 ms 2520 KB Output is correct
14 Correct 3 ms 2376 KB Output is correct
15 Correct 1 ms 2004 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3540 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 4 ms 2520 KB Output is correct
14 Correct 3 ms 2376 KB Output is correct
15 Correct 1 ms 2004 KB Output is correct
16 Correct 44 ms 38988 KB Output is correct
17 Correct 14 ms 25172 KB Output is correct
18 Correct 101 ms 58956 KB Output is correct
19 Correct 97 ms 56356 KB Output is correct
20 Correct 12 ms 25076 KB Output is correct
21 Correct 24 ms 29604 KB Output is correct
22 Correct 100 ms 65264 KB Output is correct
23 Correct 66 ms 52184 KB Output is correct
24 Correct 70 ms 51812 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3540 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 4 ms 2520 KB Output is correct
14 Correct 3 ms 2376 KB Output is correct
15 Correct 1 ms 2004 KB Output is correct
16 Correct 44 ms 38988 KB Output is correct
17 Correct 14 ms 25172 KB Output is correct
18 Correct 101 ms 58956 KB Output is correct
19 Correct 97 ms 56356 KB Output is correct
20 Correct 12 ms 25076 KB Output is correct
21 Correct 24 ms 29604 KB Output is correct
22 Correct 100 ms 65264 KB Output is correct
23 Correct 66 ms 52184 KB Output is correct
24 Correct 70 ms 51812 KB Output is correct
25 Incorrect 2 ms 3540 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 95 ms 8356 KB Output is correct
5 Correct 75 ms 8356 KB Output is correct
6 Correct 75 ms 8396 KB Output is correct
7 Correct 40 ms 7576 KB Output is correct
8 Correct 49 ms 7000 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 3540 KB Output is correct
12 Correct 2 ms 3540 KB Output is correct
13 Correct 1 ms 452 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 452 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2004 KB Output is correct
21 Correct 4 ms 2520 KB Output is correct
22 Correct 3 ms 2376 KB Output is correct
23 Correct 1 ms 2004 KB Output is correct
24 Correct 44 ms 38988 KB Output is correct
25 Correct 14 ms 25172 KB Output is correct
26 Correct 101 ms 58956 KB Output is correct
27 Correct 97 ms 56356 KB Output is correct
28 Correct 12 ms 25076 KB Output is correct
29 Correct 24 ms 29604 KB Output is correct
30 Correct 100 ms 65264 KB Output is correct
31 Correct 66 ms 52184 KB Output is correct
32 Correct 70 ms 51812 KB Output is correct
33 Incorrect 2 ms 3540 KB Output isn't correct
34 Halted 0 ms 0 KB -