Submission #981330

#	Time	Username	Problem	Language	Result	Execution time	Memory
981330		Jawad_Akbar_JJ	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	620 ms	56720 KiB

jumps

#include "jumps.h"
#include <iostream> 
#include <vector>
#include <queue>

using namespace std;
const int N = 2e5 + 10, lg = 18;
vector<int> nei[N], ch[N];
int lft[N];
int rgt[N];
int Mn[N];
int seen[N];
int idk[N];
int par[N];
bool sub1 = true;






int st[N], en[N], hei[N],Cur = 1, Par[N][lg], dt[N][lg];

void dfs(int u,int p = 0){
    hei[u] = hei[p] + 1;
    st[u] = Cur++;

    Par[u][0] = p;
    if (idk[u])
        Par[u][0] = idk[u];
    for (int i=1;i<=lg;i++)
        Par[u][i] = Par[Par[u][i-1]][i-1];

    for (int i : ch[u])
        dfs(i,u);
    en[u] = Cur++;
}








void init(int n,vector<int> h){
    vector<int> v;
    
    for (int i=0;i<n;i++)
        sub1 &= (h[i] == i + 1);

    for (int i=0;i<n;i++)
        lft[i] = rgt[i] = -1;
    
    for (int i=0;i<n;i++){
        while (v.size() > 0 and h[v.back()] < h[i])
            rgt[v.back()] = i,v.pop_back();
        v.push_back(i);
    }
    v.clear();

    for (int i=n-1;i>=0;i--){
        while (v.size() > 0 and h[v.back()] < h[i])
            lft[v.back()] = i,v.pop_back();
        v.push_back(i);
    }

    for (int i=0;i<n;i++){
        if (lft[i] != -1)
            nei[i + 1].push_back(lft[i] + 1);
        if (rgt[i] != -1)
            nei[i + 1].push_back(rgt[i] + 1);
    }


    int rt;

    for (int i=0;i<n;i++){
        if (lft[i] == -1 and rgt[i] == -1){
            rt = i + 1;
            continue;
        }
        int to = rgt[i] + 1;
        if (rgt[i] == -1 or (lft[i] != -1 and h[lft[i]] < h[rgt[i]]))
            to = lft[i] + 1;
        ch[to].push_back(i + 1);
        par[i + 1] = to;

        if (rgt[i] == -1 or lft[i] == -1)
            continue;
        idk[i + 1] = lft[i] + rgt[i] + 2 - to;
    }

    dfs(rt);
}



int dist(int A,int C){
    if ( !(st[C] <= st[A] and en[C] >= en[A]) )
        return -1;
    int d = 1;

    for (int i=lg;i>=0;i--)
        if (hei[Par[A][i]] > hei[C])
            d += (1<<i), A = Par[A][i];
    return d;
}


int cur = 0;
int minimum_jumps(int A, int B, int C, int D) {
    if (sub1)
        return C - B;

    if (A == B and C == D)
        return dist(A + 1,C + 1);

    cur++;
    queue<int> Q;

    for (int i=A+1;i<=B + 1;i++)
        Q.push(i),seen[i] = cur,Mn[i] = 0;

    while (!Q.empty()){
        int u = Q.front();
        if (u >= C+1 and u <= D+1)
            return Mn[u];
        Q.pop();
        for (int i : nei[u])
            if (seen[i] != cur)
                Mn[i] = Mn[u] + 1,Q.push(i),seen[i] = cur;
    }
    return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'void dfs(int, int)':
jumps.cpp:32:19: warning: iteration 17 invokes undefined behavior [-Waggressive-loop-optimizations]
   32 |         Par[u][i] = Par[Par[u][i-1]][i-1];
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:31:19: note: within this loop
   31 |     for (int i=1;i<=lg;i++)
      |                  ~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:94:8: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     dfs(rt);
      |     ~~~^~~~

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