結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
|
提出日時 | 2023-06-17 02:13:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 3,078 ms |
コンパイル使用メモリ | 252,500 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 19:52:18 |
合計ジャッジ時間 | 4,461 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.hpp" #else #define debug(...) 1 #endif int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; vector<int> x(n + 2), y(n + 2); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } x[n] = sx, y[n] = sy; x[n + 1] = gx, y[n + 1] = gy; auto check = [&] (int p) -> bool { const int inf = 1 << 30; vector<int> dist(n + 2, inf); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; Q.emplace(0, n); dist[n] = 0; while (!Q.empty()) { auto P = Q.top(); Q.pop(); int pos = P.second; int d = P.first; if (dist[pos] < d) { continue; } for (int i = 0; i < n + 2; i++) { int m = abs(x[pos] - x[i]) + abs(y[pos] - y[i]); int ndis = dist[pos] + max(0, (m + p - 1) / p - 1); if (ndis < dist[i]) { dist[i] = ndis; Q.emplace(ndis, i); } } } return dist[n + 1] <= k; }; int ok = 200005, ng = 0; while (ok - ng > 1) { int mid = (ok + ng) >> 1; if (check(mid)) { ok = mid; } else { ng = mid; } } cout << ok << '\n'; }