Submission #1092246

#TimeUsernameProblemLanguageResultExecution timeMemory
1092246MrPavlitoJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
217 ms63072 KiB
#include <bits/stdc++.h> //#define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second #define endl "\n" #define pii pair<int,int> using namespace std; const int MAXN = 30005; const int mod7 = 1e9+7; const long long inf = 1e18; vector<vector<pii>> graf(MAXN); vector<long long> dist(MAXN, inf); vector<set<int>> dogos(MAXN); set<pii> pq; int doge0; int doge1; void dikstra(int nod) { dist[nod] = 0; pq.insert({dist[nod], nod}); while(!pq.empty()) { auto it = pq.begin(); int u = it-> sc; pq.erase(it); for(auto x: graf[u]) { if(dist[x.fi] > dist[u] + x.sc) { pq.erase({dist[x.fi], x.fi}); dist[x.fi] = dist[u] + x.sc; pq.insert({dist[x.fi], x.fi}); } } } } signed main() { ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0); int tt=1; //cin >> tt; while(tt--) { int n,m; cin >> n >> m; for(int i=0; i<m; i++) { int a,b;cin >> a >> b; if(i==0)doge0 = a; if(i==1)doge1 = a; dogos[a].insert(b); } for(int i=0; i<n; i++) { for(auto d: dogos[i]) { int j = i; while(j+ d <n) { j+=d; graf[i].pb({j, (j-i)/d}); if(dogos[j].count(d))break; } j = i; while(j- d >=0) { j-=d; graf[i].pb({j,(i-j)/d}); if(dogos[j].count(d))break; } } } dikstra(doge0); if(dist[doge1] == inf)cout << -1 << endl; else cout << dist[doge1] << endl; } }
#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...