Submission #552632

#TimeUsernameProblemLanguageResultExecution timeMemory
552632QwertyPiJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
49 ms12680 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int, int> pii; int dp[30001]; vector<int> G[30001]; int A[30001][2]; int l[30001], r[30001]; vector<pii> H[30001]; vector<int> q[30001]; int main(){ int n, k; cin >> n >> k; set<pii> M; for(int i = 0; i < k; i++){ cin >> A[i][0] >> A[i][1]; if(i >= 2 && M.count({A[i][0], A[i][1]})){ continue; } M.insert({A[i][0], A[i][1]}); G[A[i][0]].push_back(i); H[A[i][1]].push_back({A[i][0], i}); } for(int i = 1; i <= 30000; i++){ sort(H[i].begin(), H[i].end(), [&i](pii aa, pii bb){ int a = aa.fi, b = bb.fi; return a % i < b % i || a % i == b % i && a < b; }); if(H[i].size() == 0) continue; l[H[i].front().se] = H[i].front().fi % i; for(int j = 0; j + 1 < H[i].size(); j++){ if(H[i][j].fi % i == H[i][j + 1].fi % i){ r[H[i][j].se] = H[i][j + 1].fi; l[H[i][j + 1].se] = H[i][j].fi; }else{ r[H[i][j].se] = n - 1; l[H[i][j + 1].se] = H[i][j + 1].fi % i; } } r[H[i].back().se] = n - 1; } // for(int i = 0; i < k; i++){ // cout << l[i] << ' ' << r[i] << endl; // } q[0].push_back(A[0][0]); fill(dp, dp + n, 1 << 30); for(int a = 0; a <= 30000; a++){ while(q[a].size()){ int v = q[a].back(); q[a].pop_back(); if(dp[v] != (1 << 30)) continue; dp[v] = a; for(auto i : G[v]){ for(int j = l[i]; j <= r[i]; j += A[i][1]){ int d = abs(v - j) / A[i][1]; if(dp[j] > a + d) q[a + d].push_back(j); } } } } cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl; }

Compilation message (stderr)

skyscraper.cpp: In lambda function:
skyscraper.cpp:29:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |    return a % i < b % i || a % i == b % i && a < b;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = 0; j + 1 < H[i].size(); j++){
      |                  ~~~~~~^~~~~~~~~~~~~
#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...