제출 #1059018

#제출 시각아이디문제언어결과실행 시간메모리
1059018sammyuriJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
31 ms15572 KiB
#include <bits/stdc++.h> using namespace std; /* we run dijkstra let B = 100 for all doges that have p >= b, just simulate the jumps how do we deal with the "small" doges?? note that the answer is never more than 30000... */ const int SMALL = 100; const int MAXN = 30000; const int INF = 1e9; int mintime[MAXN][SMALL + 1]; int dist[MAXN]; vector<int> doges[MAXN]; priority_queue<pair<int, int>> pq; int main() { int n; cin >> n; int m; cin >> m; for (int i = 0; i < n; i ++) for (int j = 1; j <= SMALL; j ++) mintime[i][j] = INF; for (int i = 0; i < n; i ++) dist[i] = INF; int startnode = -1, target = -1; for (int i = 0; i < m; i ++) { int b, p; cin >> b >> p; if (i == 0) startnode = b; else if (i == 1) target = b; doges[b].push_back(p); } if (startnode == target) { cout << 0 << endl; return 0; } pq.push({0, startnode}); dist[startnode] = 0; while (pq.size()) { pair<int, int> xx = pq.top(); pq.pop(); int t = -xx.first; int curnode = xx.second; if (dist[curnode] != t) continue; for (auto doge : doges[curnode]) { // big doge if (doge > SMALL) { int extratime = 0; for (int j = curnode - doge; j >= 0; j -= doge) { extratime ++; if (dist[j] > extratime + t) { dist[j] = extratime + t; pq.push({-dist[j], j}); } } extratime = 0; for (int j = curnode + doge; j < n; j += doge) { extratime ++; if (dist[j] > extratime + t) { dist[j] = extratime + t; pq.push({-dist[j], j}); } } } // small doge else { // ignore entirely if (mintime[curnode][doge] <= t) continue; mintime[curnode][doge] = t; int extratime = 0; for (int j = curnode - doge; j >= 0; j -= doge) { extratime ++; // stop if (mintime[j][doge] <= t + extratime) break; mintime[j][doge] = t + extratime; if (dist[j] > extratime + t) { dist[j] = extratime + t; pq.push({-dist[j], j}); } } extratime = 0; for (int j = curnode + doge; j < n; j += doge) { extratime ++; // stop if (mintime[j][doge] <= t + extratime) break; mintime[j][doge] = t + extratime; if (dist[j] > extratime + t) { dist[j] = extratime + t; pq.push({-dist[j], j}); } } } } if (curnode == target) { break; } } if (dist[target] == INF) { cout << -1 << endl; } else cout << dist[target] << endl; return 0; }
#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...