Submission #477409

#TimeUsernameProblemLanguageResultExecution timeMemory
477409KienTranJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
12 ms14992 KiB
#include <bits/stdc++.h> using namespace std; const int O = 3e5 + 5; const int N = 2e3 + 5; const int inf = 1e9; int n, m, b[O], p[O], d[O], c[N][N]; vector <pair <int, int>> g[O]; vector <int> a[O]; main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++ i){ cin >> b[i] >> p[i]; a[b[i]].push_back(p[i]); } for (int i = 0; i < n; ++ i){ for (int j : a[i]){ if (j == 0) continue; for (int z = i % j; z < n; z += j){ if (z != i && !c[i][z]){ c[i][z] = true; g[i].push_back({z, abs(i - z) / j}); } } } } for (int i = 0; i < n; ++ i) d[i] = inf; priority_queue <pair <int, int>> q; q.push({0, b[1]}); d[b[1]] = 0; while (q.size()){ int u = q.top().second; int du = -q.top().first; q.pop(); if (d[u] != du) continue; for (auto i : g[u]){ int v = i.first; int w = i.second; if (d[v] > d[u] + w){ d[v] = d[u] + w; q.push({-d[v], v}); } } } if (d[b[2]] >= 1e9) d[b[2]] = -1; cout << d[b[2]]; }

Compilation message (stderr)

skyscraper.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~
#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...