제출 #1227739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227739		cpdreamer	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	77 ms	7756 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1000002022;
#define F first
#define pb push_back
#define S second
#define P pair
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
bool visited[(int)1e5+1];
int r[(int)1e5+1];
int in[(int)1e5+1];
int out[(int)1e5+1];
int dep[(int)1e5+1];
V<int>adj[(int)1e5+1];
int n;
int c=0;
void dfs(int n,int p,int d) {
    dep[n]=d;
    visited[n]=true;
    in[n]=c;
    for (auto u:adj[n]) {
        if (u==p)continue;
        c++;
        dfs(u,n,d+1);
    }
    out[n]=c;
    c++;
}
void init(int N, std::vector<int> H) {
    n=N;
    stack<int>st;
    for (int i=n-1;i>=0;i--) {
        while (!st.empty()) {
            if (H[st.top()]>H[i])break;
            st.pop();
        }
        if (st.empty()) {
            r[i]=-1;
        }
        else
            r[i]=st.top();
        st.push(i);
    }
    for (int i=0;i<n;i++) {
        if (r[i]!=-1) {
            adj[i].pb(r[i]);
            adj[r[i]].pb(i);
        }
    }
    for (int i=n-1;i>=0;i--) {
        if (visited[i])continue;
        dfs(i,-1,0);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (in[C]<=in[A] && in[A]<=out[C]) {
        return dep[A]-dep[C];
    }
    return -1;
}

• Subtask 1: 0 / 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