| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 980725 | vjudge1 | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;
const ll INF = 1e9;
const ll NN = 300300;
ll up[NN][21], dw[NN][21];
int n, ok = 1;
vector<vector<ll>> v;
vector<ll> h;
void init(int N, vector<int> H)
{
n = N;
h = H;
v.resize(n);
vector<ll> q;
for(ll i = 0; i < n; ++i)
up[i][0] = -1,
dw[i][0] = -1;
for(ll i = 0; i < n; ++i)
{
ok &= h[i] == i + 1;
while(q.sz && h[q.back()] < h[i])
v[q.back()].push_back(i),
up[q.back()][0] = i,
q.pop_back();
q.push_back(i);
}
q.clear();
for(ll i = n - 1; i >= 0; --i)
{
while(q.sz && h[q.back()] < h[i])
v[q.back()].push_back(i),
dw[q.back()][0] = i,
q.pop_back();
q.push_back(i);
}
for(ll i = 0; i < n; ++i)
if(dw[i][0] > up[i][0]) swap(up[i][0], dw[i][0]);
for(ll i = 0; i < n; ++i)
if(dw[i][0] < 0) swap(up[i][0], dw[i][0]);
for(ll j = 1; j < 21; ++j)
for(ll i = 0; i < n; ++i)
{
up[i][j] = up[up[i][j - 1]][j - 1];
dw[i][j] = dw[dw[i][j - 1]][j - 1];
}
}
int minimum_jumps(int a, int b, int c, int d)
{
if(ok) return c - b;
if(a == b && c == d)
{
ll ans = 0;
for(ll j = 20; j >= 0; --j)
{
if(up[a][j] < 0) continue;
if(h[up[a][j]] <= h[d])
a = up[a][j], ans += (1 << j);
}
for(ll j = 20; j >= 0; --j)
{
if(dw[a][j] < 0) continue;
if(h[dw[a][j]] <= h[d])
a = dw[a][j], ans += (1 << j);
}
return a == d ? ans : -1;
}
vector<ll> dist(n, INF);
queue<ll> q;
for(ll i = a; i <= b; ++i)
{
dist[i] = 0;
q.push(i);
}
while(q.sz)
{
ll s = q.front();
q.pop();
for(ll t : v[s])
{
if(dist[t] < INF) continue;
dist[t] = dist[s] + 1;
q.push(t);
}
}
ll ans = INF;
for(ll i = c; i <= d; ++i)
ans = min(ans, dist[i]);
return ans < INF ? ans : -1;
}
//signed main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
//}