Submission #680167

#TimeUsernameProblemLanguageResultExecution timeMemory
680167Do_you_copyJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
642 ms7652 KiB
//Then #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ld = long double; using pii = pair <int, int>; mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e5 + 1; //const int Mod = 1e9 + 7; //const int inf = int n, m; int d[maxN]; vector <int> S[maxN]; int s, t; void Init(){ cin >> n >> m; for (int i = 1; i <= m; ++i){ int x, y; cin >> x >> y; S[x].pb(y); if (i == 1) s = x; if (i == 2) t = x; } for (int i = 0; i < n; ++i){ sort(S[i].begin(), S[i].end()); S[i].resize(unique(S[i].begin(), S[i].end()) - S[i].begin()); } priority_queue <pii, vector <pii>, greater <pii>> PQ; memset(d, 0x3f, sizeof(d)); PQ.push({0, s}); d[s] = 0; while (!PQ.empty()){ auto u = PQ.top(); PQ.pop(); if (u.fi != d[u.se]) continue; for (int j: S[u.se]){ for (int i = 1; u.se + i * j < n; ++i){ if (d[u.se + i * j] <= d[u.se] + i) continue; d[u.se + i * j] = d[u.se] + i; PQ.push({d[u.se] + i, u.se + i * j}); } for (int i = 1; u.se - i * j >= 0; ++i){ if (d[u.se - i * j] <= d[u.se] + i) continue; d[u.se - i * j] = d[u.se] + i; PQ.push({d[u.se] + i, u.se - i * j}); } } } cout << (d[t] == 0x3f3f3f3f ? -1 : d[t]); } #define debug #define taskname "test" signed main(){ faster if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } int tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000); timeout.close(); #ifndef debug cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n"; #endif // debug } }

Compilation message (stderr)

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