Submission #1260704

#TimeUsernameProblemLanguageResultExecution timeMemory
1260704tminhJakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
647 ms198244 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define endl '\n' #define fi first #define se second #define vall(a) (a).begin(), (a).end() #define sze(a) (int)a.size() #define pii pair<int, int> #define pb push_back #define pf push_front const int mod = 1e9 + 7; const signed N = 30001; const int oo = 1e9; int n, m, p[N], b[N], d[N][180], base; struct node { int idx, p, c; bool operator<(const node &other) const { return c > other.c; } }; vector<node> adj[N][180]; int dijkstra() { for (int i = 0; i < n; ++i) for (int j = 0; j <= base; ++j) d[i][j] = oo; priority_queue<node> q; d[b[0]][0] = 0; q.push({b[0], 0, d[b[0]][0]}); while(!q.empty()) { auto [idx, p, c] = q.top(); q.pop(); if (d[idx][p] != c) continue; for (auto [pos, jump, w] : adj[idx][p]) { if (d[pos][jump] > d[idx][p] + w) { d[pos][jump] = d[idx][p] + w; q.push({pos, jump, d[pos][jump]}); } } if (d[idx][0] > d[idx][p]) { d[idx][0] = d[idx][p]; q.push({idx, 0, d[idx][0]}); } if (p != 0) { if (idx + p < n && d[idx + p][p] > d[idx][p] + 1) { d[idx + p][p] = d[idx][p] + 1; q.push({idx + p, p, d[idx + p][p]}); } if (idx - p >= 0 && d[idx - p][p] > d[idx][p] + 1) { d[idx - p][p] = d[idx][p] + 1; q.push({idx - p, p, d[idx - p][p]}); } } } return (d[b[1]][0] == oo ? -1 : d[b[1]][0]); } void output() { for (int i = 0; i < m; ++i) { if (p[i] > base) { for (int j = 1; b[i] + p[i] * j < n; ++j) adj[b[i]][0].pb({b[i] + p[i] * j, 0, j}); for (int j = 1; b[i] - p[i] * j >= 0; ++j) adj[b[i]][0].pb({b[i] - p[i] * j, 0, j}); } else adj[b[i]][0].pb({b[i], p[i], 0}); } cout << dijkstra(); return; } void input() { cin >> n >> m; base = sqrtl(n); for (int i = 0; i < m; ++i) cin >> b[i] >> p[i]; output(); return; } signed main () { if(fopen("", "r")) { freopen("", "r", stdin); freopen("", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); input(); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~
#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...