제출 #984104

#제출 시각아이디문제언어결과실행 시간메모리
984104Marcus밀림 점프 (APIO21_jumps)C++17
21 / 100
268 ms48720 KiB
#include "jumps.h" #include <vector> #include <bits/stdc++.h> using namespace std; int n; vector<int> h; const int INF = 2e6; vector<vector<int>> adj(2000); vector<vector<int>> dist(2000, vector<int>(2000, INF)); int powtwo = (int)pow(2, __lg(2000) + !!(2000 & (2000-1))); void bfs(int x) { queue<int> q; vector<bool> visited(n); int start = x; visited[start] = true; dist[start][start] = 0; q.push(start); while (!q.empty()) { int s = q.front(); q.pop(); for (auto u : adj[s]) { if (visited[u]) continue; visited[u] = true; dist[start][u] = dist[start][s]+1; q.push(u); } } } struct SegmentTree { vector<int> t; SegmentTree(int power) : t(2*power) {} void build(vector<int>& a, int v, int tl, int tr) { if (tl == tr) { if (tl < (int)a.size()) t[v] = a[tl]; else t[v] = INF; } else { int tm = (tl + tr) / 2; build(a, v*2, tl, tm); build(a, v*2+1, tm+1, tr); t[v] = min(t[v*2], t[v*2+1]); } } int query(int v, int tl, int tr, int l, int r) { if (l > r) return INF; if (l == tl && r == tr) return t[v]; int tm = (tl + tr) / 2; return min(query(v*2, tl, tm, l, min(r, tm)), query(v*2+1, tm+1, tr, max(l, tm+1), r)); } }; vector<SegmentTree> segdist; void init(int N, std::vector<int> H) { n = N; for (auto u: H) {h.push_back(u);} h.shrink_to_fit(); for (int i=0; i<n; i++) { for (int j=i; j<n; j++) { if (h[i] < h[j]) {adj[i].push_back(j); break;}; } for (int j=i; j>=0; j--) { if (h[i] < h[j]) {adj[i].push_back(j); break;}; } } for (int i=0; i<n; i++) {bfs(i);} for (int i=0; i<n; i++) { SegmentTree segtree(powtwo); segtree.build(dist[i], 1, 0, powtwo-1); segdist.push_back(segtree); } } int minimum_jumps(int A, int B, int C, int D) { int answer = INF; for (int i=A; i<=B; i++) { answer = min(answer, segdist[i].query(1, 0, powtwo-1, C, D)); } return (answer >= INF ? -1 : answer); }
#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...