제출 #971148

#제출 시각아이디문제언어결과실행 시간메모리
971148dubabuba밀림 점프 (APIO21_jumps)C++14
4 / 100
580 ms16788 KiB
#include <bits/stdc++.h> #include "jumps.h" using namespace std; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxn = 2e5 + 10; vector<int> adj[mxn]; int dis[mxn], h[mxn]; bool gay = 1; void init(int N, vector<int> H) { vector<int> L(N, -1), R(N, -1); stack<int> st; st.push(0); for(int i = 1; i < N; i++) { while(st.size() && H[st.top()] <= H[i]) st.pop(); if(st.size()) L[i] = st.top(); st.push(i); } stack<int> en; en.push(0); for(int i = N - 1; i >= 0; i--) { while(en.size() && H[en.top()] <= H[i]) en.pop(); if(en.size()) R[i] = en.top(); en.push(i); } for(int i = 0; i < N; i++) { h[i] = H[i]; if(L[i] > -1) adj[i].push_back(L[i]); if(R[i] > -1) adj[i].push_back(R[i]); } for(int i = 1; i < N; i++) if(H[i] <= H[i - 1]) gay = 0; } map<pii, int> mp; int solve(int u, int v) { if(h[u] >= h[v]) return INT_MAX; auto it = mp.find(MP(u, v)); if(it != mp.end()) return (*it).ss; int ret = INT_MAX; for(int t : adj[u]) ret = min(ret, solve(t, v)); return mp[MP(u, v)] = ret; } int minimum_jumps(int A, int B, int C, int D) { if(gay) return C - B; if(A == B && C == D) cout << solve(A, C) << endl; memset(dis, -1, sizeof dis); priority_queue<pii> pq; for(int i = A; i <= B; i++) { pq.push(MP(0, i)); } while(pq.size()) { int d = -pq.top().ff; int u = pq.top().ss; pq.pop(); if(dis[u] > -1) continue; dis[u] = d; for(int v : adj[u]) if(dis[v] == -1) pq.push(MP(-(d + 1), v)); } int ans = INT_MAX; for(int i = C; i <= D; i++) if(dis[i] > -1) ans = min(ans, dis[i]); return (ans == INT_MAX) ? -1 : 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...