제출 #743483

#제출 시각아이디문제언어결과실행 시간메모리
743483saayan007밀림 점프 (APIO21_jumps)C++17
0 / 100
437 ms1048576 KiB
#include "bits/stdc++.h" using namespace std; #define fr first #define sc second #define eb emplace_back const char nl = '\n'; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif vector<int> L, R; vector<vector<int>> dist; int n; const int inf = 2e8L + 1; vector<int> tp; void init(int N, std::vector<int> H) { n = N; L.resize(n); stack<int> st; for(int i = 0; i < n; ++i) { while(!st.empty() && H[st.top()] < H[i]) st.pop(); L[i] = (st.empty() ? -1 : st.top()); st.push(i); } while(!st.empty()) st.pop(); R.resize(n); for(int i = n - 1; i >= 0; --i) { while(!st.empty() && H[st.top()] < H[i]) st.pop(); R[i] = (st.empty() ? -1 : st.top()); st.push(i); } /* for(int i = 0; i < N; ++i) { */ /* cout << i << " : " << L[i] << ' ' << R[i] << nl; */ /* } */ tp.resize(n); iota(tp.begin(), tp.end(), 0); sort(tp.begin(), tp.end(), [&](int left, int right) { return H[left] < H[right]; }); /* for(int i : tp) cout << i << ' '; cout << nl; */ dist = vector<vector<int>>(n, vector<int>(n, -1)); for(int i = 0; i < n; ++i) dist[i][i] = 0; /* for(int x = 0; x < n; ++x) { */ /* dist[x][x] = 0; */ /* queue<int> q; */ /* q.emplace(x); */ /* while(!q.empty()) { */ /* int y = q.front(); q.pop(); */ /* if(L[y] != -1 && dist[x][L[y]] == -1) { */ /* dist[x][L[y]] = dist[x][y] + 1; */ /* q.emplace(L[y]); */ /* } */ /* if(R[y] != -1 && dist[x][R[y]] == -1) { */ /* dist[x][R[y]] = dist[x][y] + 1; */ /* q.emplace(R[y]); */ /* } */ /* } */ /* for(int y = 0; y < n; ++y) { */ /* /1* cout << dist[x][y] << ' '; *1/ */ /* if(dist[x][y] == -1) dist[x][y] = 10*n; */ /* } */ /* /1* cout << nl; *1/ */ /* } */ } int bfs(int st, int nd) { int res = inf; queue<int> q; q.emplace(st); while(!q.empty()) { int x = q.front(); q.pop(); if(dist[x][nd] != -1) { res = min(res, dist[st][x] + dist[x][nd]); continue; } if(x == nd) { return dist[st][nd] = res; } if(L[x] != -1 && dist[st][L[x]] == -1) { dist[st][L[x]] = dist[st][x] + 1; q.emplace(L[x]); } if(R[x] != -1 && dist[st][R[x]] == -1) { dist[st][R[x]] = dist[st][x] + 1; q.emplace(R[x]); } } return dist[st][nd] = res; } int minimum_jumps(int A, int B, int C, int D) { int res = bfs(A, C); return res > n ? -1 : res; }
#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...