結果
問題 | No.1998 Manhattan Restaurant |
ユーザー |
![]() |
提出日時 | 2024-12-02 14:30:58 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,609 bytes |
コンパイル時間 | 2,610 ms |
コンパイル使用メモリ | 212,104 KB |
実行使用メモリ | 822,752 KB |
最終ジャッジ日時 | 2024-12-02 14:31:58 |
合計ジャッジ時間 | 52,199 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 MLE * 3 |
other | AC * 11 TLE * 18 MLE * 2 |
ソースコード
#include <bits/stdc++.h>#define INF 4611686018427387903llusing namespace std;using ll = long long;bool func(ll n, vector<vector<pair<int, ll> > >& graph, ll mid) {vector<int> parity(n, -1);for(int sv = 0; sv < n; ++sv){if(parity[sv] != -1){continue;}parity[sv] = 0;vector<int> stk = {sv};while(!stk.empty()){int v = stk[stk.size() - 1]; stk.pop_back();for(auto&[nv, nd] : graph[v]){if(nd <= mid){continue;}if(parity[nv] == -1){parity[nv] = parity[v] ^ 1;stk.push_back(nv);}else if(parity[nv] == parity[v]){return false;}}}}return true;}int main(){int n; cin >> n;vector<pair<ll, ll> > p(n);for(auto&[x, y] : p){cin >> x >> y;}vector<vector<pair<int, ll> > > graph(n, vector<pair<int, ll> >({}));for(int i = 0; i < n - 1; ++i){auto&[x1, y1] = p[i];for(int j = i + 1; j < n; ++j){auto&[x2, y2] = p[j];ll d = abs(x1 - x2) + abs(y1 - y2);graph[i].push_back({j, d});graph[j].push_back({i, d});}}ll ok = INF, ng = -1;while(abs(ok - ng) > 1){ll mid = (ok + ng) / 2;if(func(n, graph, mid)){ok = mid;}else{ng = mid;}}ll ans = ok / 2;cout << ans << endl;return 0;}