제출 #565630

#제출 시각아이디문제언어결과실행 시간메모리
565630MurotY밀림 점프 (APIO21_jumps)C++14
25 / 100
4069 ms21572 KiB
#include "jumps.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int N=2*1e5+7; vector <int> a; vector <int> g[N]; bool u[N], u1[N]; int dp[2006][2006]; bool ok=1; int n; void init(int N, std::vector<int> H) { n=N; a=H; for (int i=0;i<n-1;i++){ if (a[i] > a[i+1]) { ok=0; break; } } if (!ok){ vector <int> v; for (int i=n-1;i>=0;i--){ while (!v.empty() && a[i] > a[v.back()]) v.pop_back(); if (!v.empty()) g[i].push_back(v.back()); v.push_back(i); } v.clear(); for (int i=0;i<n;i++){ while (!v.empty() && a[i] > a[v.back()]) v.pop_back(); if (!v.empty()) g[i].push_back(v.back()); v.push_back(i); } if (n <= 2000){ for (int i=0;i<n;i++){ for (int j=0;j<n;j++) dp[i][j]=1e9; queue <int> q; q.push(i); dp[i][i]=0; while (!q.empty()){ int x1=q.front(); q.pop(); for (auto l:g[x1]){ if (dp[i][l] > dp[i][x1]+1){ dp[i][l]=dp[i][x1]+1; q.push(l); } } } } } } } int minimum_jumps(int A, int B, int C, int D) { if (ok) return C-B; int ans=1e9; if (n <= 2000){ for (int i=A;i<=B;i++){ for (int j=C;j<=D;j++){ ans=min(ans, dp[i][j]); } } if (ans == 1e9) ans=-1; return ans; } queue <int> q; int d[N]; for (int i=0;i<n;i++) d[i]=1e9, q.push(i); for (int i=A;i<=B;i++) q.push(i), d[i]=0; while (!q.empty()){ int x=q.front(); for (auto l:g[x]){ if (d[l] > d[x]+1) { d[l]=d[x]+1; q.push(l); } } } for (int i=C;i<=D;i++) ans=min(ans, d[i]); if (ans == 1e9) ans=-1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...