Submission #652774

#TimeUsernameProblemLanguageResultExecution timeMemory
652774alvinpiterJakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
1 ms608 KiB
/* 5 3 0 2 1 1 4 1 */ #include<bits/stdc++.h> using namespace std; #define INF 1000000000 #define MAXN 2000 #define MAXP 2000 int n, m, startPosition, startPower, endPosition, dist[MAXN + 3][MAXP + 3]; vector<int> dogesAtPosition[MAXN + 3]; int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int b, p; cin >> b >> p; if (i == 0) { startPosition = b; startPower = p; } if (i == 1) { endPosition = b; } dogesAtPosition[b].push_back(p); } for (int i = 0; i < n; i++) { sort(dogesAtPosition[i].begin(), dogesAtPosition[i].end()); dogesAtPosition[i].erase(unique(dogesAtPosition[i].begin(), dogesAtPosition[i].end()), dogesAtPosition[i].end()); } for (int i = 0; i < n; i++) { for (int p = 1; p <= MAXP; p++) { dist[i][p] = INF; } } dist[startPosition][startPower] = 0; priority_queue<pair<int, pair<int, int> > > pq; pq.push({-dist[startPosition][startPosition], {startPosition, startPower}}); while (!pq.empty()) { auto [d, state] = pq.top(); pq.pop(); auto [position, power] = state; d *= -1; // Hacky if (d > dist[position][power]) { continue; } // Pass to other doge for (auto p: dogesAtPosition[position]) { if (dist[position][p] > dist[position][power]) { dist[position][p] = dist[position][power]; pq.push({-dist[position][p], {position, p}}); } } // Jump for (int direction = -1; direction <= 1; direction += 2) { int newPosition = position + direction * power; if (newPosition >= 0 && newPosition < n && dist[newPosition][power] > dist[position][power] + 1) { dist[newPosition][power] = dist[position][power] + 1; pq.push({-dist[newPosition][power], {newPosition, power}}); } } } int ans = INF; for (int p = 1; p <= MAXP; p++) { ans = min(ans, dist[endPosition][p]); } if (ans < INF) { cout << ans << endl; } else { cout << -1 << 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...