Submission #1190478

#TimeUsernameProblemLanguageResultExecution timeMemory
1190478SulARainforest Jumps (APIO21_jumps)C++20
0 / 100
3 ms5880 KiB
#include <bits/stdc++.h> #define bitcount __builtin_popcountll #define all(a) (a).begin(), (a).end() using namespace std; vector<int> adj[200000]; int dist[200000]; int bfs(vector<int> start, vector<int> end) { memset(dist, -1, sizeof dist); queue<int> q; for (int u : start) { dist[u] = 0; q.push(u); } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } int res = 1e9; for (int x : end) if (dist[x] != -1) res = min(res, dist[x]); for (int i = 0; i < 7; cout << dist[i++] << " \n"[i == 7]); return res == 1e9 ? -1 : res; } void init(int n, vector<int> h) { vector<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && h[i] > h[st.back()]) st.pop_back(); if (!st.empty()) adj[i].push_back(st.back()); st.push_back(i); } st.clear(); for (int i = n-1; i >= 0; i--) { while (!st.empty() && h[i] > h[st.back()]) st.pop_back(); if (!st.empty()) adj[i].push_back(st.back()); st.push_back(i); } for (int i = 0; i < n; i++) { for (int j : adj[i]) cout << j << " "; cout << '\n'; } } int minimum_jumps(int a, int b, int c, int d) { vector<int> start, end; for (int i = a; i <= b; i++) start.push_back(i); for (int i = c; i <= d; i++) end.push_back(i); return bfs(start, end); }
#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...