結果
問題 |
No.1998 Manhattan Restaurant
|
ユーザー |
![]() |
提出日時 | 2024-12-01 21:07:09 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 940 bytes |
コンパイル時間 | 513 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 671,360 KB |
最終ジャッジ日時 | 2024-12-02 13:59:04 |
合計ジャッジ時間 | 64,872 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 MLE * 2 |
other | AC * 6 TLE * 9 MLE * 16 |
ソースコード
import sys input = sys.stdin.readline N = int(input()) P = [list(map(int, input().split())) for _ in [0] * N] graph = [[] for _ in [0] * N] for i in range(N - 1): for j in range(i + 1, N): d = abs(P[i][0] - P[j][0]) + abs(P[i][1] - P[j][1]) graph[i].append((j, d)) graph[j].append((i, d)) def func(d): c = [0] * N for v in range(N): if(c[v]): continue c[v] = 1 que = [v] while(que): now = que.pop() for nv, nd in graph[now]: if(nd <= d): continue if(c[nv] == 0): c[nv] = -c[now] que.append(nv) elif(c[nv] == c[now]): return False return True ok = 4 * 10 ** 9 + 1 ng = 0 while(abs(ok - ng) > 1): d = (ok + ng) // 2 if(func(d)): ok = d else: ng = d ans = ok // 2 print(ans)