Submission #110245

#TimeUsernameProblemLanguageResultExecution timeMemory
110245hugo_pmJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
940 ms96520 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse2,sse3,ssse3,sse4,avx,avx2,tune=native") #include <bits/stdc++.h> using namespace std; #define form2(i, a, b) for (int i = (a); i < (b); ++i) #define ford2(i, a, b) for (int i = (a-1); i >= (b); --i) #define form(i, n) form2(i, 0, n) #define ford(i, n) ford2(i, n, 0) #define chmax(x, v) x = max(x, (v)) #define chmin(x, v) x = min(x, (v)) #define fi first #define se second const int BIG = 2*(int)(1e9); typedef long long ll; typedef long double ld; typedef pair<int, int> pii; void solve(); signed main() { ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; } const int borneSuj = 30*1000 + 5; const int borneTab = 200*borneSuj; int gt[borneSuj][200]; int inv[borneTab]; bool witPrev[borneTab]; bool witSuiv[borneTab]; int arr = -1, dep=-1; int nbPlaces, nbDoges, nbNoeuds; int limSqd; vector<int> doge[borneSuj]; void solve() { cin >> nbPlaces >> nbDoges; chmax(nbPlaces, 20); nbNoeuds = nbPlaces; limSqd = sqrt(nbPlaces); form2(distance, 1, limSqd) { form(ini, distance) { for (int place = ini; place < nbPlaces; place += distance) { int corNod = nbNoeuds; ++nbNoeuds; inv[corNod] = place+1; gt[place][distance] = corNod; if (place != ini) { witPrev[corNod] = true; witSuiv[corNod-1] = true; } } } } form(iDoge, nbDoges) { int pos, saut; cin >> pos >> saut; if (iDoge == 0) dep = pos; if (iDoge == 1) arr = pos; doge[pos].push_back(saut); } vector<int> md(nbNoeuds, BIG); vector<int> etat(nbNoeuds, 2); deque<int> m1; m1.push_front(dep); md[dep] = 0; while (! m1.empty()) { int nod = m1.front(); m1.pop_front(); etat[nod] = 0; int dis = md[nod]; auto propag = [&] (int vo, int poids) { if (etat[vo] == 2) { m1.push_back(vo); etat[vo] = 1; md[vo] = dis + poids; } else if (etat[vo] == 1) { chmin(md[vo], dis + poids); } else { if (dis+poids < md[vo]) { md[vo] = dis+poids; etat[vo] = 1; m1.push_back(vo); } } }; if (nod < nbPlaces) { int pos = nod; for (int saut : doge[nod]) { if (saut < limSqd) { propag(gt[pos][saut], 0); } else { for (int dd = 1; pos + dd*saut < nbPlaces; ++dd) { propag(pos+dd*saut, dd); } for (int dd = 1; pos - dd*saut >= 0; ++dd) { propag(pos-dd*saut, dd); } } } } if (nod >= nbPlaces) { if (inv[nod]) propag(inv[nod]-1, 0); if (witPrev[nod]) propag(nod-1, 1); if (witSuiv[nod]) propag(nod+1, 1); } } if (md[arr] == BIG) cout << "-1\n"; else cout << md[arr] << "\n"; }
#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...