Submission #722074

#	Time	Username	Problem	Language	Result	Execution time	Memory
722074		irmuun	Rainforest Jumps (APIO21_jumps)	C++17	60 / 100	4090 ms	54404 KiB

jumps

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

const int maxn=200005,INF=1e9,lg=24;
bool ok=true;
vector<int>adj[maxn+5];
int n,high[lg][maxn],low[lg][maxn],h[maxn],dist[maxn];

int get_path(int *x,int y,int jmp[][maxn]){
    int tot=0;
    for(int i=20;i>=0;i--){
        if(jmp[i][*x]!=-1&&h[jmp[i][*x]]<=h[y]){
            *x=jmp[i][*x];
            tot+=(1<<i);
        }
    }
    return tot;
}

int sub5(int x,int y){
    int num1=get_path(&x,y,high);
    int num2=get_path(&x,y,low);
    if(h[x]==h[y]) return num1+num2;
    else return -1;
}
void calc(int jmp[][maxn]){
    for(int i=1;i<lg;i++){
        for(int j=0;j<n;j++){
            if(jmp[i-1][j]!=-1){
                jmp[i][j]=jmp[i-1][jmp[i-1][j]];
            }
        }
    }
}

int dfs(int a,int b,int c,int d){
    queue<int>q;
    fill(dist,dist+n+1,INF);
    for(int i=a;i<=b;i++) q.push(i), dist[i]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(c<=x&&x<=d) return dist[x];
        for(auto u:adj[x]){
            if(dist[u]==INF){
                dist[u]=dist[x]+1;
                q.push(u);
            }
        }
    }
    return -1;
}

void init(int N,vector<int>H){
    n=N;
    memset(low,-1,sizeof(low));
    memset(high,-1,sizeof(high));
    vector<int>pr(n,-1),nx(n,-1);
    for(int i=0;i<n;i++){
        h[i]=H[i];
        if(H[i]!=i+1) ok=false;
    }
    stack<pair<int,int>>s;
    for(int i=0;i<n;i++){
        while(!s.empty()&&s.top().ff<H[i]) s.pop();
        if(!s.empty()) pr[i]=s.top().ss;
        s.push({H[i],i});
    }
    while(!s.empty()) s.pop();
    for(int i=n-1;i>=0;i--){
        while(!s.empty()&&s.top().ff<H[i]) s.pop();
        if(!s.empty()) nx[i]=s.top().ss;
        s.push({H[i],i});
    }
    for(int i=0;i<n;i++){
        if(pr[i]!=-1) adj[i].pb(pr[i]);
        if(nx[i]!=-1) adj[i].pb(nx[i]);
        if(pr[i]!=-1&&nx[i]!=-1){
            if(h[pr[i]]<h[nx[i]]) swap(pr[i],nx[i]);
            high[0][i] = pr[i]; low[0][i] = nx[i];
            if(h[pr[i]]>h[nx[i]]) swap(pr[i],nx[i]);
        }
        else{
            if(pr[i]!=-1) low[0][i] = pr[i];
            else low[0][i] = nx[i];
        }
    }
    calc(low);
    calc(high);
}

int minimum_jumps(int A, int B, int C, int D){
    if(ok==true) return C-B;
    if(A==B&&C==D) return sub5(B,C);
    else return dfs(A,B,C,D);
}

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