제출 #659270

#제출 시각아이디문제언어결과실행 시간메모리
659270ssenseJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
704 ms262144 KiB
#include <bits/stdc++.h> #define startt ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; using namespace std; #define vint vector<int> #define all(v) v.begin(), v.end() #define MOD 1000000007 #define MOD2 998244353 #define MX 1000000000 #define MXL 1000000000000000000 #define PI (ld)2*acos(0.0) #define pb push_back #define sc second #define fr first //#define int long long #define endl '\n' #define ld long double #define NO cout << "NO" << endl #define YES cout << "YES" << endl //mesanu int mp[30000][175]; vector<pair<int, int>> adj[30000*175]; int now = 1; void cnn(int first, int second) { mp[first][second] = now; now++; } int dijkstra(int s, int e) { int n = now; vector<int> d(n, MX); d[s] = 0; priority_queue<pair<int, int>> q; q.push({0, s}); while (!q.empty()) { int v = q.top().second; int dist = -q.top().first; q.pop(); if(dist != d[v]) { continue; } for (auto edge : adj[v]) { int to = edge.first; int len = edge.second; if (d[v] + len < d[to]) { d[to] = d[v] + len; q.push({-d[to], to}); } } } return d[e]; } void solve() { int n, m; cin >> n >> m; int start = 0; int end = 0; int th = sqrt(n); for(int sky = 0; sky < n; sky++) { cnn(sky, 0); } map<pair<int, int>, bool> used; for(int i = 0; i < m; i++) { int sky, power; cin >> sky >> power; if(i == 0) { start = sky; } if(i == 1) { end = sky; } if(used[{sky,power}]) { continue; } used[{sky, power}] = true; if(power <= th) { if(mp[sky][power] != 0) { adj[mp[sky][0]].pb({mp[sky][power], 0}); continue; } if(mp[sky%power][power] == 0) { for(int j = sky%power; j < n; j+=power) { if(mp[j][power] == 0) { cnn(j, power); } adj[mp[j][power]].pb({mp[j][0], 0}); if(j+power < n) { cnn(j+power, power); adj[mp[j][power]].pb({mp[j+power][power], 1}); adj[mp[j+power][power]].pb({mp[j][power], 1}); } } } adj[mp[sky][0]].pb({mp[sky][power], 0}); } else { for(int j = sky%power; j < n; j+=power) { adj[mp[sky][0]].pb({mp[j][0], abs(sky-j)/power}); } } } used.clear(); int dist = dijkstra(mp[start][0], mp[end][0]); if(dist == MX) { cout << -1 << endl; } else { cout << dist << endl; } } int32_t main(){ startt int t = 1; //cin >> t; while (t--) { solve(); } } /* 5 3 0 2 1 1 4 1 */
#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...