제출 #1047862

#제출 시각아이디문제언어결과실행 시간메모리
1047862Maite_Morale밀림 점프 (APIO21_jumps)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define vll vector<ll> #define MAX 500005 #define oo 1e18 #define pll pair<ll,ll> #define F first #define S second const ll bts=20; pll p[MAX],s[bts+10][MAX],t[bts+10][MAX]; ll d[MAX],N; pll query(ll x,ll y){ if(x>y)return {0,N}; ll c=log2l(abs(x-y)+1); return max(t[c][x],t[c][y-(1LL<<c)+1]); } void init(int n, std::vector<int> H) { H.push_back(0);N=n;pll rt={0,n}; for(int i=0;i<=n;i++){ t[0][i]={H[i],i}; rt=max(rt,t[0][i]); } for(int i=1;i<=bts;i++){ for(int j=0;j<=n;j++){ t[i][j]=max(t[i-1][j],t[i-1][j+(1LL<<(i-1))]); } } queue<pair<ll,pll>> q; q.push({rt.S,{0,n-1}}); d[n]=0;s[0][n]={n,n}; d[rt.S]=1;s[0][rt.S]={n,n}; while(!q.empty()){ pair<ll,pll> u=q.front();q.pop(); pair<ll,pll> h1={query(u.S.F,u.F-1).S,{u.S.F,u.F-1}}; if(h1.F!=n){ d[h1.F]=d[u.F]+1; p[h1.F]={h1.S.F-1,h1.S.S+1}; s[0][h1.F].F=u.S.F-1; s[0][h1.F].S=u.F; q.push(h1); } pair<ll,pll> h2={query(u.F+1,u.S.S).S,{u.F+1,u.S.S}}; if(h2.F!=n){ d[h2.F]=d[u.F]+1; p[h2.F]={h2.S.F-1,h2.S.S+1}; s[0][h2.F].F=u.S.S+1; s[0][h2.F].S=u.F; q.push(h2); } } for(int i=0;i<=n;i++){ if(s[0][i].F==-1)s[0][i].F=n; if(s[0][i].S==-1)s[0][i].S=n; } for(int i=1;i<=bts;i++){ for(int j=0;j<=n;j++){ s[i][j].F=s[i-1][s[i-1][j].F].F; s[i][j].S=s[i-1][s[i-1][j].S].S; } } } /* int minimum_jumps(int A, int B, int C, int D) { swap(B,C); if(A<=p[B].F)return -1; ll r=0; for(int i=bts;i>=0;i--){ if(d[s[i][A].F]>=d[B]){ r+=(1LL<<i); A=s[i][A].F; } } for(int i=bts;i>=0;i--){ if(d[s[i][A].S]>=d[B]){ r+=(1LL<<i); A=s[i][A].S; } } return r; } int main() { int N, Q; assert(2 == scanf("%d %d", &N, &Q)); std::vector<int> H(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &H[i])); } init(N, H); for (int i = 0; i < Q; ++i) { int A, B, C, D; assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D)); printf("%d\n", minimum_jumps(A, B, C, D)); } return 0; } /* 7 4 3 2 1 6 4 5 7 4 4 6 6 1 1 5 5 0 0 2 2 5 5 6 6 */

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

jumps.cpp:100:1: warning: "/*" within comment [-Wcomment]
  100 | /*
      |  
/usr/bin/ld: /tmp/ccokJh5j.o: in function `main':
stub.cpp:(.text.startup+0x1d1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status