oj.uz

답안 #984321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984321 2024-05-16T13:21:26 Z Marcus 밀림 점프 (APIO21_jumps) C++17
23 / 100
 782 ms 42768 KB 
#include "jumps.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> h;
const int INF = 2e6;
vector<vector<int>> adj(2e5);
int k;
vector<vector<int>> st1;
vector<vector<int>> st2;
 
void init(int N, std::vector<int> H) {
    n = N;
    for (auto u: H) {h.push_back(u);}
    h.shrink_to_fit();

    stack<int> pre;
    for (int i=0; i<n; i++)
    {
        while (!pre.empty() && h[pre.top()] < h[i])
        {
            pre.pop();
        }
        if (!pre.empty()) adj[i].push_back(pre.top());
        pre.push(i);
    }
    
    stack<int> suff;
    for (int i=n-1; i>=0; i--)
    {
        while (!suff.empty() && h[suff.top()] < h[i])
        {
            suff.pop();
        }
        if (!suff.empty()) adj[i].push_back(suff.top());
        suff.push(i);
    }

    //for (int i=0; i<n; i++)
    //{
    //    for (int j=i; j<n; j++)
    //    {
    //        if (h[i] < h[j]) {adj[i].push_back(j); break;};
    //    }
    //    for (int j=i; j>=0; j--)
    //    {
    //        if (h[i] < h[j]) {adj[i].push_back(j); break;};
    //    }
    //}

    k = (int)__lg(n);
    st1.resize(k+1); for (auto &u: st1) {u.resize(n, -1);}
    st2.resize(k+1); for (auto &u: st2) {u.resize(n, -1);} 

    for (int j = 0; j < n; j++)
    {
        if (adj[j].size() == 2)
        {
            int x = adj[j][0]; int y = adj[j][1];
            if (h[x] > h[y]) {st1[0][j] = x; st2[0][j] = y;}
            else {st1[0][j] = y; st2[0][j] = x;}
        }
        else if (adj[j].size() == 1)
        {
            int x = adj[j][0];
            st2[0][j] = x;
        }
    }

    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (st1[i-1][j] != -1) st1[i][j] = st1[i-1][st1[i-1][j]];
            if (st2[i-1][j] != -1) st2[i][j] = st2[i-1][st2[i-1][j]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int answer = 0;
    int point = A;
    for (int i = k; i >= 0; i--) {
        if (st1[i][point] != -1 && h[st1[i][point]] <= h[C]) {
            answer += (int)pow(2, i);
            point = st1[i][point];
        }
        if (point == C) return answer;
    }
    for (int i = k; i >= 0; i--) {
        if (st2[i][point] != -1 && h[st2[i][point]] <= h[C]) {
            answer += (int)pow(2, i);
            point = st2[i][point];
        }
        if (point == C) return answer;
    }
    return -1;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 112 ms 35080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 180 ms 21132 KB Output is correct
5 Correct 682 ms 41836 KB Output is correct
6 Correct 415 ms 10576 KB Output is correct
7 Correct 655 ms 41856 KB Output is correct
8 Correct 389 ms 17028 KB Output is correct
9 Correct 699 ms 41840 KB Output is correct
10 Correct 767 ms 42744 KB Output is correct
11 Correct 728 ms 42188 KB Output is correct
12 Correct 702 ms 42604 KB Output is correct
13 Correct 687 ms 41840 KB Output is correct
14 Correct 717 ms 42364 KB Output is correct
15 Correct 668 ms 42552 KB Output is correct
16 Correct 641 ms 42620 KB Output is correct
17 Correct 1 ms 4952 KB Output is correct
18 Correct 2 ms 4952 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct
21 Correct 4 ms 4952 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Correct 3 ms 4952 KB Output is correct
24 Correct 3 ms 4952 KB Output is correct
25 Correct 2 ms 4952 KB Output is correct
26 Correct 2 ms 5208 KB Output is correct
27 Correct 10 ms 5404 KB Output is correct
28 Correct 13 ms 5464 KB Output is correct
29 Correct 14 ms 5464 KB Output is correct
30 Correct 12 ms 5208 KB Output is correct
31 Correct 11 ms 5408 KB Output is correct
32 Correct 1 ms 4952 KB Output is correct
33 Correct 30 ms 25456 KB Output is correct
34 Correct 60 ms 41912 KB Output is correct
35 Correct 45 ms 42584 KB Output is correct
36 Correct 51 ms 41836 KB Output is correct
37 Correct 49 ms 42368 KB Output is correct
38 Correct 45 ms 42740 KB Output is correct

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 180 ms 21132 KB Output is correct
5 Correct 682 ms 41836 KB Output is correct
6 Correct 415 ms 10576 KB Output is correct
7 Correct 655 ms 41856 KB Output is correct
8 Correct 389 ms 17028 KB Output is correct
9 Correct 699 ms 41840 KB Output is correct
10 Correct 767 ms 42744 KB Output is correct
11 Correct 728 ms 42188 KB Output is correct
12 Correct 702 ms 42604 KB Output is correct
13 Correct 687 ms 41840 KB Output is correct
14 Correct 717 ms 42364 KB Output is correct
15 Correct 668 ms 42552 KB Output is correct
16 Correct 641 ms 42620 KB Output is correct
17 Correct 1 ms 4952 KB Output is correct
18 Correct 2 ms 4952 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct
21 Correct 4 ms 4952 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Correct 3 ms 4952 KB Output is correct
24 Correct 3 ms 4952 KB Output is correct
25 Correct 2 ms 4952 KB Output is correct
26 Correct 2 ms 5208 KB Output is correct
27 Correct 10 ms 5404 KB Output is correct
28 Correct 13 ms 5464 KB Output is correct
29 Correct 14 ms 5464 KB Output is correct
30 Correct 12 ms 5208 KB Output is correct
31 Correct 11 ms 5408 KB Output is correct
32 Correct 1 ms 4952 KB Output is correct
33 Correct 30 ms 25456 KB Output is correct
34 Correct 60 ms 41912 KB Output is correct
35 Correct 45 ms 42584 KB Output is correct
36 Correct 51 ms 41836 KB Output is correct
37 Correct 49 ms 42368 KB Output is correct
38 Correct 45 ms 42740 KB Output is correct
39 Correct 2 ms 4952 KB Output is correct
40 Correct 2 ms 4952 KB Output is correct
41 Correct 1 ms 4952 KB Output is correct
42 Correct 161 ms 21088 KB Output is correct
43 Correct 608 ms 42164 KB Output is correct
44 Correct 415 ms 10576 KB Output is correct
45 Correct 683 ms 41840 KB Output is correct
46 Correct 390 ms 17088 KB Output is correct
47 Correct 703 ms 41908 KB Output is correct
48 Correct 728 ms 42604 KB Output is correct
49 Correct 749 ms 42088 KB Output is correct
50 Correct 782 ms 42608 KB Output is correct
51 Correct 665 ms 41852 KB Output is correct
52 Correct 755 ms 42164 KB Output is correct
53 Correct 696 ms 42768 KB Output is correct
54 Correct 689 ms 42628 KB Output is correct
55 Correct 1 ms 4952 KB Output is correct
56 Incorrect 85 ms 41580 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 112 ms 35080 KB Output isn't correct
4 Halted 0 ms 0 KB -