Submission #297618

#TimeUsernameProblemLanguageResultExecution timeMemory
297618AaronNaiduJakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
352 ms169808 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, b, p; vector<int> doges[50000]; vector<pair<int, int> > graph[50000]; int powers[50000]; int positions[50000]; priority_queue<pair<int, int> > q; int dists[50000]; bool visited[50000]; bool visited2[3000][3000]; //position then power set<int> powerPos[50000]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = 0; i < m; i++) { cin >> b >> p; powers[i] = p; positions[i] = b; doges[b].push_back(i); powerPos[positions[i]].insert(powers[i]); } for (int i = 0; i < n; i++) { dists[i] = 1000000000; } int checkCount = 0; for (int i = 0; i < m; i++) { int jumpCount = 0; for (int j = positions[i]+powers[i]; j < n; j+=powers[i]) { jumpCount++; checkCount++; graph[positions[i]].push_back({j, jumpCount}); //cout << "Connecting " << j << " to " << positions[i] << "\n"; if (powerPos[j].find(powers[i]) != powerPos[j].end()) { break; } } jumpCount = 0; for (int j = positions[i]-powers[i]; j >= 0; j-=powers[i]) { jumpCount++; checkCount++; graph[positions[i]].push_back({j, jumpCount}); //cout << "Connecting " << j << " to " << positions[i] << "\n"; if (powerPos[j].find(powers[i]) != powerPos[j].end()) { break; } } assert(checkCount < 10000000); } /*for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << matrix[i][j] << " "; } cout << "\n"; }*/ q.push({0, positions[0]}); dists[positions[0]] = 0; while (!q.empty()) { int x = q.top().second; //cout << "At node " << x << " which is " << dists[x] << " away\n"; if (x == positions[1]) { int ans = dists[positions[1]]; cout << ans << "\n"; return 0; } q.pop(); if (visited[x]) { continue; } visited[x] = true; for (auto i : graph[x]) { if (!visited[i.first] and dists[x] + i.second < dists[i.first]) { dists[i.first] = dists[x] + i.second; q.push({-dists[i.first], i.first}); //cout << "Pushing " << i.first << " which is " << dists[i.first] << " away\n"; } } } cout << "-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...