oj.uz

Submission #439028

# Submission time Handle Problem Language Result Execution time Memory
439028 2021-06-29T05:43:23 Z aris12345678 Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 4000 ms 487104 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 200005;
bool sub1 = false;
vector<int> height;

void init(int n, vector<int> h) {
    if(is_sorted(h.begin(), h.end()))
        sub1 = true;
    height = h;
}

int bfs(int i, int end) {
    int n = int(height.size());
    queue<pair<int, int> > q;
    q.push({i, 0});
    while(!q.empty()) {
        int u = q.front().first, jumps = q.front().second;
        q.pop();
        if(u == end)
            return jumps;
        if(height[u] > height[end]) continue;
        int j = u;
        while(j >= 0 && height[j] <= height[u])
            j--;
        // cout << "bfs_1: " << u << " " << j << " " << jumps+1 << "\n";
        if(j >= 0)
            q.push({j, jumps+1});
        j = u;
        while(j < n && height[j] <= height[u])
            j++;
        // cout << "bfs_2: " << u << " " << j << " " << jumps+1 << "\n";
        if(j < n)
            q.push({j, jumps+1});
    }
    return -1;
}

int minimum_jumps(int a, int b, int c, int d) {
    if(sub1)
        return c-b;
    else {
        int ans = INT_MAX;
        for(int i = a; i <= b; i++) {
            int pos = i;
            for(int j = c; j <= d; j++) {
                if(height[j] < height[i]) continue;
                int jumps = bfs(pos, j);
                // cout << i << " " << j << " " << jumps << "\n";
                if(jumps != -1)
                    ans = min(ans, jumps);
            }
        }
        if(ans == INT_MAX)
            return -1;
        return ans;
    }
}

/*
int main() {
    int n = 7;
    vector<int> h = {3, 2, 1, 6, 4, 5, 7};
    init(n, h);
    int a = 0, b = 1, c = 2, d = 2;
    printf("%d\n", minimum_jumps(a, b, c, d));
    return 0;
}
*/

/*
0 1 2 3 4 5 6
3 2 1 6 4 5 7

(1, 3)
(5, 6)
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 189 ms 2112 KB Output is correct
4 Correct 1530 ms 2580 KB Output is correct
5 Correct 977 ms 1428 KB Output is correct
6 Correct 1050 ms 2576 KB Output is correct
7 Correct 1138 ms 1856 KB Output is correct
8 Correct 1291 ms 2532 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Correct 23 ms 200 KB Output is correct
7 Correct 43 ms 200 KB Output is correct
8 Correct 22 ms 200 KB Output is correct
9 Correct 7 ms 200 KB Output is correct
10 Correct 56 ms 200 KB Output is correct
11 Correct 3 ms 200 KB Output is correct
12 Correct 1278 ms 200 KB Output is correct
13 Correct 954 ms 200 KB Output is correct
14 Correct 72 ms 200 KB Output is correct
15 Execution timed out 4059 ms 487104 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Correct 23 ms 200 KB Output is correct
7 Correct 43 ms 200 KB Output is correct
8 Correct 22 ms 200 KB Output is correct
9 Correct 7 ms 200 KB Output is correct
10 Correct 56 ms 200 KB Output is correct
11 Correct 3 ms 200 KB Output is correct
12 Correct 1278 ms 200 KB Output is correct
13 Correct 954 ms 200 KB Output is correct
14 Correct 72 ms 200 KB Output is correct
15 Execution timed out 4059 ms 487104 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Execution timed out 4017 ms 2056 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 350 ms 1344 KB Output is correct
5 Correct 2194 ms 2600 KB Output is correct
6 Correct 961 ms 584 KB Output is correct
7 Execution timed out 4054 ms 2700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 350 ms 1344 KB Output is correct
5 Correct 2194 ms 2600 KB Output is correct
6 Correct 961 ms 584 KB Output is correct
7 Execution timed out 4054 ms 2700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 189 ms 2112 KB Output is correct
4 Correct 1530 ms 2580 KB Output is correct
5 Correct 977 ms 1428 KB Output is correct
6 Correct 1050 ms 2576 KB Output is correct
7 Correct 1138 ms 1856 KB Output is correct
8 Correct 1291 ms 2532 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Correct 23 ms 200 KB Output is correct
15 Correct 43 ms 200 KB Output is correct
16 Correct 22 ms 200 KB Output is correct
17 Correct 7 ms 200 KB Output is correct
18 Correct 56 ms 200 KB Output is correct
19 Correct 3 ms 200 KB Output is correct
20 Correct 1278 ms 200 KB Output is correct
21 Correct 954 ms 200 KB Output is correct
22 Correct 72 ms 200 KB Output is correct
23 Execution timed out 4059 ms 487104 KB Time limit exceeded
24 Halted 0 ms 0 KB -