제출 #771263

#제출 시각아이디문제언어결과실행 시간메모리
771263IBoryJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
986 ms262144 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 = 5555555; vector<int> G[MAX]; vector<int> C[30003]; bool noL[MAX], noR[MAX]; int D[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; map<pii, vector<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}].push_back(b); } int node = N + 1, SN, EN; for (auto& [q, v] : make) { auto [p, i] = q; if (!i) i += p; vector<int> fr; for (int j = i; j <= N; j += p) { if (S == pii{ j, p }) SN = node; if (E == pii{ j, p }) EN = node; C[j].push_back(node); fr.push_back(node++); } noL[fr[0]] = noR[fr.back()] = 1; for (int n : v) { G[n].push_back(-fr[(n - 1) / p]); } } make.clear(); for (int i = 1; i <= N; ++i) { noL[i] = noR[i] = 1; for (int n : C[i]) { G[n].push_back(-i); } C[i].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 (!noL[cur]) G[cur].push_back(cur - 1); if (!noR[cur]) G[cur].push_back(cur + 1); 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); } if (!noL[cur]) G[cur].pop_back(); if (!noR[cur]) G[cur].pop_back(); } cout << (D[EN] > 1E9 ? -1 : D[EN]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:80:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |  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...