Submission #1193945

#TimeUsernameProblemLanguageResultExecution timeMemory
1193945uranhishigRainforest Jumps (APIO21_jumps)C++20
0 / 100
1 ms504 KiB
// #include "jumps.h" #include <bits/stdc++.h> #include <cassert> #include <cstdio> #include <vector> using namespace std; const int mx = 2000; vector<vector<int>> dst(mx); vector<vector<int>> adj(mx); int n; void init(int N, std::vector<int> H) { queue<pair<int, int>> q; n = N; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dst[i][j] = INT_MAX; } } for (int i = 0; i < n -1 ; i++) { for (int j = i + 1; j < n; j++) { if(H[i] > H[j]) { adj[i].push_back(j); } } } for (int i = 1; i < n ; i++) { for (int j = i - 1; j < n; j++) { if(H[i] > H[j]) { adj[i].push_back(j); } } } // while(!q.empty()) { // q.push({}) // } } void bfs(int start, int end) { queue<pair<int, int>> q; vector<bool> vis(4000); vis[start] = true; q.push({start, 0}); while (!q.empty()) { int X = q.front().first; int dist = q.front().second; q.pop(); for(auto Y:adj[X]){ if(!vis[Y]){ vis[Y] = 1; dst[start][Y] = dst[start][X] + 1; } } } } int minimum_jumps(int A, int B, int C, int D) { int sta, end; for (int i = A; i <= B; i++) { for (int j = C; j <= D; j++) { sta = i; end = j; } } bfs(sta, end); int ans = 1e9; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans = min(ans, dst[i][j]); } } if(ans==1e9) return -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...