# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
981666 | IUA_Hasin | 밀림 점프 (APIO21_jumps) | C++17 | 579 ms | 2044 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll M = 2e3+10;
ll N2;
vector<ll> graph[M];
vector<ll> H2;
ll vis[M];
ll level[M][M];
ll status2;
void bfs(ll source){
queue<ll> q;
q.push(source);
vis[source] = 1;
level[source][source] = 0;
while(!q.empty()){
ll temp = q.front();
q.pop();
for(auto u : graph[temp]){
if(vis[u]==0){
q.push(u);
level[source][u] = level[source][temp]+1;
vis[u] = 1;
}
}
}
}
void init(int N, std::vector<int> H) {
ll stat = 1;
for(int i=0; i<N2-1; i++){
if(H[i+1]!=H[i]){
stat = -1;
break;
}
}
status2 = stat;
if(stat==-1){
N2 = N;
vector<ll> v[N+1];
for(int i=0; i<N; i++){
ll a = H[i];
v[a].push_back(i);
H2.push_back(a);
}
set<ll> s;
for(int i=0; i<N; i++){
s.insert(i);
}
for(int i=1; i<=N; i++){
if(i==N){
break;
}
ll ind = v[i][0];
ll val = H[ind];
//cout<<ind<<" "<<val<<endl;
auto it1 = s.lower_bound(ind);
auto it2 = s.upper_bound(ind);
it1--;
ll temp1, temp2;
if(it1!=s.end()){
temp1 = *it1;
temp1 = H[temp1];
graph[val].push_back(temp1);
}
if(it2!=s.end()){
temp1 = *it2;
temp1 = H[temp1];
graph[val].push_back(temp1);
}
auto itt = s.find(ind);
s.erase(itt);
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
level[i][j] = -1;
}
}
for(int i=1; i<=N; i++){
for(int j=0; j<=N; j++){
vis[j] = 0;
}
bfs(i);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(status2==1){
return C-B;
} else {
ll status = -1;
ll ans = M+100;
for(int i=A; i<=B; i++){
for(int j=C; j<=D; j++){
ll start = H2[i];
ll end = H2[j];
ll temp = level[start][end];
if(temp>=0){
status = 1;
ans = min(ans, temp);
}
}
}
// if(status2==1){
// return C-B;
// }
if(status==-1){
return -1;
} else {
return ans;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |