Submission #477988

#TimeUsernameProblemLanguageResultExecution timeMemory
477988MarceantasyJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
511 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array const int mxN = 3e4+10, M = 1e9+7; int n, m, b[mxN], p[mxN], dis[mxN]; vector<ar<int, 2>> adj[mxN]; set<ar<int, 2>> s; void dijkstra(){ priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> pq; memset(dis, 0x3f, sizeof(dis)); pq.push({dis[b[0]] = 0, b[0]}); while(pq.size()){ ar<int, 2> cur = pq.top(); pq.pop(); int v = cur[1]; for(ar<int, 2> u : adj[v]){ if(dis[u[0]] > dis[v] + u[1]){ dis[u[0]] = dis[v] + u[1]; pq.push({dis[u[0]], u[0]}); } } } } int main(){ cin >> n >> m; for(int i = 0; i<m; ++i){ cin >> b[i] >> p[i]; s.insert({b[i], p[i]}); } for(auto v : s){ for(int h = v[0]+v[1]; h<n; h+=v[1]){ adj[v[0]].push_back({h, (h-v[0])/v[1]}); } for(int h = v[0]-v[1]; h>=0; h-=v[1]){ adj[v[0]].push_back({h, (v[0]-h)/v[1]}); } } dijkstra(); cout << (dis[b[1]] >= 1e9?-1:dis[b[1]]) << "\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...