Submission #709916

#TimeUsernameProblemLanguageResultExecution timeMemory
709916noeditJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1081 ms40112 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; const int INF = 1e9; const int B = 315; const int MAXN = 3e4 + 5; vector<pair<int, int> > d; int dist[MAXN][B]; vector<short> sm[MAXN]; vector<short> bg[MAXN]; signed main() { //ifstream cin("input.txt"); //ofstream cout("output.txt"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; d.resize(m); vector<int> big; for (int i = 0; i < m; i++) { cin >> d[i].first >> d[i].second; if (d[i].second >= B) { big.push_back(i); bg[d[i].first].push_back(d[i].second); } else { sm[d[i].first].push_back(d[i].second); } } for (int i = 0; i < n; i++) for (int j = 0; j < B; j++) dist[i][j] = INF; priority_queue<array<int, 3> > st; st.push({0, d[0].first, 0}); dist[d[0].first][0] = 0; while (!st.empty()) { auto [dst, pos, pw] = st.top(); dst = -dst; st.pop(); if (dst > dist[pos][pw]) continue; if (dst != dist[pos][pw]) continue; if (pw > 0) { vector<array<short, 3> > to; if (pos - pw >= 0) { if (dist[pos - pw][pw] > dst + 1) { //st.erase({dist[pos - pw][pw], pos - pw, pw}); dist[pos - pw][pw] = dst + 1; st.push({-dist[pos - pw][pw], pos - pw, pw}); } if (dist[pos - pw][0] > dst + 1) { //st.erase({dist[pos - pw][0], pos - pw, 0}); dist[pos - pw][0] = dst + 1; st.push({-dist[pos - pw][0], pos - pw, 0}); } } if (pos + pw < n) { if (dist[pos + pw][pw] > dst + 1) { //st.erase({dist[pos + pw][pw], pos + pw, pw}); dist[pos + pw][pw] = dst + 1; st.push({-dist[pos + pw][pw], pos + pw, pw}); } if (dist[pos + pw][0] > dst + 1) { //st.erase({dist[pos + pw][0], pos + pw, 0}); dist[pos + pw][0] = dst + 1; st.push({-dist[pos + pw][0], pos + pw, 0}); } } continue; } for (auto& mv : bg[pos]) { for (int j = pos, k = 0; j < n; j += mv, k++) { if (dist[j][0] > dst + k) { dist[j][0] = dst + k; st.push({-dist[j][0], j, 0}); } } for (int j = pos, k = 0; j >= 0; j -= mv, k++) { if (dist[j][0] > dst + k) { dist[j][0] = dst + k; st.push({-dist[j][0], j, 0}); } } } for (auto& mv : sm[pos]) { if (dist[pos][mv] > dst + 0) { dist[pos][mv] = dst + 0; st.push({-dist[pos][mv], pos, mv}); } } } int mn = INF; for (int i = 0; i < B; i++) mn = min(mn, dist[d[1].first][i]); if (mn == INF) cout << -1; else cout << mn; return 0; } /* small (i, j) -1> (i - j, 0), (i + j, 0) (i, 0) -0> (i, j) (i, j) -1> (i - j, j), (i + j, j) large (i, 0) -1> (i + j, 0) (i, 0) -1> (i - j, 0) */
#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...