Submission #771277

#TimeUsernameProblemLanguageResultExecution timeMemory
771277IBoryJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1063 ms114436 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define pii pair<int, int> using namespace std; const int MAX = 7777777; vector<int> G[30003]; int D[MAX], L[MAX]; pii B[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; map<pii, set<int>> make; pii S, E; for (int i = 0; i < M; ++i) { int b, p; cin >> b >> p; b++; if (i == 0) S = { b, p }; if (i == 1) E = { b, p }; make[{p, b % p}].insert(b); } int node = N + 1, SN, EN; for (auto& [q, v] : make) { auto [p, i] = q; if (!i) i += p; vector<int> fr; int init = node; B[init] = { p, i }; for (int j = i; j <= N; j += p) { if (S == pii{ j, p }) SN = node; if (E == pii{ j, p }) EN = node; L[node] = init; fr.push_back(node++); } for (int n : v) { G[n].push_back(-fr[(n - 1) / p]); } } L[node] = 1; make.clear(); memset(D, 0x3f, sizeof(D)); D[SN] = 0; deque<int> Q; Q.push_back(SN); while (!Q.empty()) { int cur = Q.front(); Q.pop_front(); if (cur == EN) break; if (cur <= N) { for (int next : G[cur]) { int d = 1; if (next < 0) { d = 0; next *= -1; } if (D[cur] + d >= D[next]) continue; D[next] = D[cur] + d; if (d == 0) Q.push_front(next); else Q.push_back(next); } } else { vector<int> AG; int t = L[cur]; int RN = B[t].second + B[t].first * (cur - t); if (L[cur] != cur) AG.push_back(cur - 1); if (L[cur + 1] != (cur + 1)) AG.push_back(cur + 1); AG.push_back(-RN); for (int next : AG) { int d = 1; if (next < 0) { d = 0; next *= -1; } if (D[cur] + d >= D[next]) continue; D[next] = D[cur] + d; if (d == 0) Q.push_front(next); else Q.push_back(next); } } } cout << (D[EN] > 1E9 ? -1 : D[EN]); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:91:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^
#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...