Submission #569366

#	Time	Username	Problem	Language	Result	Execution time	Memory
569366		BadPenalty	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4091 ms	24008 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 2e5+10,mod = 1e9+7;
vector<int>A,adj[N];
int n,dst[N];
bool vstd[N];

void init(int N, std::vector<int> H)
{
    n = N;
    A = H;
    set<int>s;
    s.insert(A[0]);
    for(int i = 1;i<n;i++)
    {
        while(!s.empty()&&*s.begin()<A[i])
            s.erase(s.begin());
        if(!s.empty())
            adj[A[i]].pb(*s.begin());
        s.insert(A[i]);
    }
    s.clear();
    s.insert(A[n-1]);
    for(int i = n-2;i>=0;i--)
    {
        while(!s.empty()&&*s.begin()<A[i])
            s.erase(s.begin());
        if(!s.empty())
            adj[A[i]].pb(*s.begin());
        s.insert(A[i]);
    }

    return;
}

int minimum_jumps(int a, int B, int C, int D)
{
    for(int i = 0;i<n;i++)
        vstd[i] = 0,dst[A[i]] = 1e9;
    queue<int>q;
    for(int i = a;i<=B;i++)
    {
        q.push(A[i]);
        dst[A[i]] = 0;
    }
    while(!q.empty())
    {
        int nd = q.front();
        q.pop();
        if(vstd[nd])continue;
        vstd[nd] = 1;

        for(auto u:adj[nd])
        {
            if(dst[u]>dst[nd]+1)
            {
                dst[u] = dst[nd]+1;
                q.push(u);
            }
        }
    }
    int ans = 1e9;
    for(int i = C;i<=D;i++)
    {
        ans = min(ans,dst[A[i]]);
    }
    if(ans!=1e9)
    return ans;
    return -1;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19