oj.uz

Submission #657664

# Submission time Handle Problem Language Result Execution time Memory
657664 2022-11-10T16:15:32 Z activedeltorre Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 1 ms 2640 KB 
#include "jumps.h"

#include <vector>
#include <stack>
#include <queue>
using namespace std;
stack <int>st;
int v[100005];
vector<int>adj[100005];
int n;
void init(int N, vector<int> H)
{
    int i;
    n=N;
    for(i=1; i<=n; i++)
    {
        v[i]=H[i-1];
    }
    v[0]=1e8;
    st.push(0);
    for(i=1; i<=n; i++)
    {
        if(v[i]>v[st.top()])
        {
            adj[st.top()].push_back(i);
            st.pop();
        }
        st.push(i);
    }
    while(st.size())
    {
        st.pop();
    }
    st.push(n+1);
    v[n+1]=1e8;
    for(i=n; i>=1; i--)
    {
        if(v[i]>v[st.top()])
        {
            adj[st.top()].push_back(i);
            st.pop();
        }
        st.push(i);
    }
    while(st.size())
    {
        st.pop();
    }
}
queue<int>qu;
int rasp[100005];
int minimum_jumps(int a, int b, int c, int d)
{
    int i,k,curr;
    for(i=1;i<=n;i++)
    {
        rasp[i]=1e8;
    }
    if(a>b)
    {
        swap(a,b);
    }
    if(c>d)
    {
        swap(c,d);
    }
    for(i=a;i<=b;i++)
    {
        qu.push(i);
        rasp[i]=0;
    }
    while(qu.size())
    {
        curr=qu.front();
        qu.pop();
        if(curr>=c && curr<=d)
        {
            return rasp[curr];
        }
        for(i=0;i<adj[curr].size();i++)
        {
            k=adj[curr][i];
            if(rasp[k]>rasp[curr]+1)
            {
                rasp[k]=rasp[curr]+1;
                qu.push(k);
            }
        }
    }
    return -1;
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(i=0;i<adj[curr].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -