제출 #1035878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035878		_8_8_	Rainforest Jumps (APIO21_jumps)	C++17	컴파일 에러	0 ms	0 KiB

jumps

#include "jumps.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int B = 20;
int n;
vector<vector<int>> build(vector<vector<int>> g,vector<int>rt){
    vector<vector<int>> up(n+1);
    function<void(int,int )> dfs = [&](int v,int pr) {
        up[v].resize(B);
        up[v][0] = pr;
        for(int i = 1;i < B;i++){
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
        for(int to:g[v]) {  
            dfs(to,v);
        }
    };
    for(int i:rt) {
        dfs(i,i);
    }
    return up;
}
vector<vector<int>> up,up1,up2;
const int maxn = (int)2e5 + 12;
int l[maxn],r[maxn];
vector<int> h;
bool te[maxn];
void init(int N, vector<int> H) {
    h = H;
    n = N;
    vector<int> st,rt;
    vector<vector<int>> G(n);
    for(int i = 0;i < N;i++) {
        while(!(int)st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
            l[i] = -1;
        }else {
            G[st.back()].push_back(i);            
            l[i] = st.back();
        }
        st.push_back(i);
    }
    up = build(G,rt);
    for(int i = 0;i < n;i++){
        G[i].clear();
    }
    rt.clear();
    st.clear();
    for(int i = N - 1;i >= 0;i--){
        while(!st.empty() && H[st.back()] < H[i]){
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
            r[i] = -1;
        }else {
            G[st.back()].push_back(i);
            r[i] = st.back();
        }
        st.push_back(i);
    }
    up1 = build(G,rt);
    for(int i = 0;i < n;i++){
        G[i].clear();
    }
    rt.clear();
    int _x;
    for(int i = 0;i < n;i++) {
        if(l[i] == r[i] && l[i] == -1) {
            _x = i;
            continue;
        }
        if(r[i] == -1) {
            G[l[i]].push_back(i);
        }else {
            if(l[i] == -1 || H[l[i]] < H[r[i]]){
                G[r[i]].push_back(i);
            }else {
                G[l[i]].push_back(i);
            }
        }
    }
    rt.push_back(_x);
    up2 = build(G,rt);
}
int glob;
bool check(int ver,int C,int D){
    int sum = 0;
    for(int i = B - 1;i >= 0;i--){
        if(up1[ver][i] < C){
            ver = up1[ver][i];
            sum += (1 << i);
        }
    }
    sum++;;
    glob = sum;
    ver = up1[ver][0];
    return (ver >= C && ver <= D);
}
int go(int ver,int C,int D) {
    // return 1;
    auto bad = [&](int x) -> bool {
        if(!check(x,C,D)) return true;
        if(x >= C && x <= D) return true;
        if(r[x] >= C && r[x] <= D) return true;
        return false;
    };
    int ans = 0;
    assert(check(ver,C,D));
    if(!bad(up2[ver][0],C,D)) {
        for(int i = B - 1;i >= 0;i--) {
            if(!bad(up2[ver][i])){
                ver = up2[ver][i];
                ans += (1 << i);
            }   
        }
        ans++;
        ver = up2[ver][0];
    }
    check(ver,C,D);
    ans += glob;
    return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
    if(!check(B,C,D)) return -1;
    int ver = B;
    for(int i = 19;i >= 0;i--){
        if(up[ver][i] >= A && check(up[ver][i],C,D)){
            ver = up[ver][i];
        }
    }
    if(r[ver] >= C && r[ver] <= D) return 1;
    return go(ver,C,D);
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int go(int, int, int)':
jumps.cpp:116:28: error: no match for call to '(go(int, int, int)::<lambda(int)>) (__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, int&, int&)'
  116 |     if(!bad(up2[ver][0],C,D)) {
      |                            ^
jumps.cpp:108:16: note: candidate: 'go(int, int, int)::<lambda(int)>'
  108 |     auto bad = [&](int x) -> bool {
      |                ^
jumps.cpp:108:16: note:   candidate expects 1 argument, 3 provided