제출 #1202369

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

jumps

#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 500'005;

int n;
vector<vector<int>> edgelist;
vector<vector<int>> pow2parent;

void init(int N, std::vector<int> H) {
    n = N;
    edgelist = vector<vector<int>> (N+2);
    edgelist[0] = {0, 0};
    edgelist[N+1] = {0, 0};
    pow2parent = vector<vector<int>> (N+2, vector<int> (20, 0));
    set<int> trees;
    trees.insert(0);
    trees.insert(N+1);
    set<int> hanging_trees;
    hanging_trees.insert(0);
    hanging_trees.insert(-N-1);

    vector<pii> heightmap;
    vector<int> newH(N+2, 0);
    for (int i=0; i<N; i++)
    {
        heightmap.push_back({H[i], i+1});
        newH[i+1] = H[i];
    }
        
    sort(heightmap.begin(), heightmap.end());
    for (int ind=N-1; ind>=0; ind--)
    {
        int next_tall = heightmap[ind].second;
        int aa = 0 - *(hanging_trees.lower_bound(0-next_tall));
        int bb =     *(        trees.lower_bound(  next_tall));
        edgelist[next_tall].push_back(aa);
        edgelist[next_tall].push_back(bb);
        hanging_trees.insert(0-next_tall);
        trees.insert(next_tall);

        int parent;
        if (newH[aa] >= newH[bb])
            parent = aa;
        else
            parent = bb;
        pow2parent[next_tall][0] = parent;
        for (int i=1; i<=19; i++)
            pow2parent[next_tall][i] = pow2parent[ pow2parent[next_tall][i-1] ][i-1];
    }
}

bool went_too_high(int node, int C)
{
    if (node <= 0)
        return 1;
    if (node >= (n+1))
        return 1;
    if ((edgelist[node][0] <= C) and (C <= edgelist[node][1]))
        return 1;
    return 0;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    
    int jumps_so_far = 0;
    int curr = A;
    for (int pow = 19; pow>=0; pow--)
    {
        int candidate = pow2parent[curr][pow];
        if (went_too_high(pow2parent[candidate][0], C) == 0)
        {
            jumps_so_far = jumps_so_far + (1<<pow);
            curr = candidate;
        }
    }
    if (edgelist[curr][0] == C)
        return jumps_so_far+1;
    if (edgelist[curr][1] == C)
        return jumps_so_far+1;
    if (edgelist[edgelist[curr][0]][0] == C)
        return jumps_so_far+2;
    if (edgelist[edgelist[curr][0]][1] == C)
        return jumps_so_far+2;
    if (edgelist[edgelist[curr][1]][0] == C)
        return jumps_so_far+2;
    if (edgelist[edgelist[curr][1]][1] == C)
        return jumps_so_far+2;
    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