Submission #589732

#TimeUsernameProblemLanguageResultExecution timeMemory
589732Error42Road Construction (JOI21_road_construction)C++17
100 / 100
9101 ms46616 KiB
#include <algorithm> #include <climits> #include <iostream> #include <queue> #include <set> #include <map> using namespace std; using ll = long long; int main() { int n, k; cin >> n >> k; map<ll, set<ll>> points; for (int i = 0; i < n; i++) { ll x, y; cin >> x >> y; points[x].insert(y); } ll worst_dist = (ll)INT_MAX * 5ll; priority_queue<ll> best_dists; for (auto cur_it_x = points.begin(); cur_it_x != points.end(); ++cur_it_x) { auto cur_x = cur_it_x->first; const auto& cur_ys = cur_it_x->second; for (const auto& cur_y : cur_ys) { for (auto cmp_it_x = cur_it_x; cmp_it_x != points.end(); ++cmp_it_x) { const auto cmp_x = cmp_it_x->first; if (cmp_x > cur_x + worst_dist) break; auto dist_x = abs(cur_x - cmp_x); for (auto cmp_it_y = cmp_it_x->second.lower_bound(cur_y - worst_dist); cmp_it_y != cmp_it_x->second.end(); ++cmp_it_y) { const auto cmp_y = *cmp_it_y; if (cmp_y - cur_y + dist_x > worst_dist) break; if (cmp_x == cur_x && cmp_y == cur_y) break; auto dist = dist_x + abs(cur_y - cmp_y); best_dists.push(dist); if (best_dists.size() > k) { best_dists.pop(); worst_dist = best_dists.top(); } } } } } vector<ll> ans; while (!best_dists.empty()) { ans.push_back(best_dists.top()); best_dists.pop(); } reverse(ans.begin(), ans.end()); for (auto x : ans) cout << x << "\n"; }

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:54:43: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |                     if (best_dists.size() > k) {
      |                         ~~~~~~~~~~~~~~~~~~^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...