結果
| 問題 |
No.3351 Towering Tower
|
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2025-11-10 23:51:28 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,687 bytes |
| コンパイル時間 | 238 ms |
| コンパイル使用メモリ | 82,240 KB |
| 実行使用メモリ | 81,944 KB |
| 最終ジャッジ日時 | 2025-11-13 21:14:10 |
| 合計ジャッジ時間 | 7,296 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 27 |
ソースコード
"""
i >= 1
(u, v) について、
- h[u] = h[v] <= x のとき (u, v) と (v, u) が存在
- h[u] = h[v] > x のとき どちらも存在しない
- h[u] < h[v] のとき、
i >= (h[u] - x) / (h[v] - h[u]) のとき、(u, v) が存在
- h[u] - x <= 0 のとき、常に(u, v) が存在
i <= (x - h[v]) / (h[v] - h[u]) のとき、(v, u) が存在
- x - h[v] <= 0 のとき、常に(v, u) は存在しない
- h[u] < h[v] とする
- x < h[u] のとき (u, v) は i >= d(u, v) のとき存在、(v, u) は存在しない
- x > h[v] のとき (v, u) は i <= d(u, v) のとき存在、(u, v) 常に存在
- h[u] <= x <= h[v] のとき、(u, v) は常に存在、(v, u) は存在しない
2 (n + 1) 頂点で考える
(頂点、パリティ)で考えたときに、
h[i] <= x のとき、
h[i] > x になったら、常に h[i] は狭義単調増加、逆戻りもできない
h[i] <= x のときに、どれだけ回数を稼げるかになる。
n, a[1], a[2], ..., a[s], a[s+1], ...
h[a[i]] <= x (i <= s)
x < h[a[s+1]] < h[a[s+2]] < ...
各h[i] <= x となる頂点について、訪れることが出来る最大の時刻を求める
d(u, v) < inf のとき、 d(v, u) = inf が成り立つ
(2 * (n + 1) 頂点で考える)
回数の稼ぎ方として、長さ 2 より大きいループはいらない
(なぜなら、ループの最後に現れた頂点との往復に置き換えれるから)
また、往復する辺は高々 1個だけでいい。
よって、ある辺で、往復したときの最大時刻を求めて
"""
MAX = 5
from collections import deque
def solve(n, h, g):
inf = 10 ** 18
idx = sorted(range(n), key=lambda x: h[x])
h = h + [-1]
def check(x):
h[n] = x
N = 2 * (n + 1)
"""
h[i] <= x の頂点の最短距離
"""
dist = [-1] * N
from collections import deque
dq = deque()
for i in g[n]:
if h[i] <= x:
dist[i * 2 + 1] = 1
dq.append(i * 2 + 1)
dist[n * 2] = 0
while dq:
ui, uj = divmod(dq.popleft(), 2)
vj = uj ^ 1
for vi in g[ui]:
if h[vi] <= x:
if h[ui] == h[vi]:
if dist[vi * 2 + vj] == -1:
dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
dq.append(vi * 2 + vj)
elif h[ui] < h[vi]:
if dist[vi * 2 + vj] == -1:
dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
dq.append(vi * 2 + vj)
else:
L = (x - h[ui]) // (h[ui] - h[vi])
if L >= dist[ui * 2 + uj]:
if dist[vi * 2 + vj] == -1:
dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
dq.append(vi * 2 + vj)
final = list(dist)
for _ in range(2):# 二回やることで、もとに戻るのも考慮
for ui in range(n + 1):
if h[ui] > x:
continue
for uj in range(2):
if dist[ui * 2 + uj] == -1:
continue
for vi in g[ui]:
if h[vi] > x:
continue
vj = uj ^ 1
# ui -> vi にできるだけ往復する
d1 = inf
d2 = inf
if h[ui] < h[vi]:
d2 = (x - h[vi]) // (h[vi] - h[ui])
elif h[ui] > h[vi]:
d1 = (x - h[ui]) // (h[ui] - h[vi])
if d1 >= dist[ui * 2 + uj]:
# uj + 2 * k <= d1 の時に u -> v
# uj + 2 * k - 1 <= d2 v -> u
k = min((d1 - uj) // 2 + 1, (d2 - uj + 1) // 2)
final[vj * 2 + vi] = max(final[vj * 2 + vi], uj + 2 * k + 1)
# print(final)
# h[u] <= x < h[v]
def transition(ui):
for uj in range(2):
if final[ui * 2 + uj] == -1:
continue
for vi in g[ui]:
if h[vi] <= x:
continue
if h[ui] >= h[vi]:
continue
vj = uj ^ 1
d = (h[ui] - x - 1) // (h[vi] - h[ui]) + 1
if final[ui * 2 + uj] >= d:
# print((ui, uj), "->", (vi, vj), d)
final[vi * 2 + vj] = max(final[vi * 2 + vj], final[ui * 2 + uj] + 1)
for ui in idx:
if h[ui] > x:
break
transition(ui)
transition(n)
for ui in idx:
if h[ui] <= x:
continue
transition(ui)
# print(dist, final)
return all(final[i * 2] != -1 or final[i * 2 + 1] != -1 for i in range(n))
ok = MAX
ng = -1
while ok - ng > 1:
mid = (ok + ng) // 2
res = check(mid)
# print(mid, res)
if res:
ok = mid
else:
ng = mid
return ok
for _ in range(int(input())):
n, m = map(int, input().split())
h = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
print(solve(n, h, g))