結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー satos---jp
提出日時 2026-05-02 19:37:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 2,875 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 210 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 85,120 KB
スコア 1,412,206
最終ジャッジ日時 2026-05-02 19:37:45
合計ジャッジ時間 9,966 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

N, T = map(int, input().split())

ps = []
A = []
for y in range(N):
    row = list(map(int, input().split()))
    for x,v in enumerate(row):
      ps.append((v,(y,x)))
    A.append(row)
    
ps = sorted(ps)[::-1]


class UF:
  def __init__(self,N):
    self.v = [i for i in range(N)]
  
  def root(self,x):
    if self.v[x]==x:
      return x
    else:
      t = self.root(self.v[x])
      self.v[x] = t
      return t

  def union(self,a,b):
    self.v[self.root(a)] = self.root(b)
  
  def same(self,a,b):
    return self.root(a) == self.root(b)

def solve(k):
  n = N
  ts = [v[1] for v in ps[:k]]
  # print(ts[:10])

  # gen dss
  dss = []
  for s in range(k):
    for t in range(s):
      (fy,fx) = ts[s]
      (ty,tx) = ts[t]
      # print(s,t,(fx,fy))
      dss.append(((abs(fx-tx)+abs(fy-ty)),(s,t)))
  
  dss = sorted(dss)
  uf = UF(k)
  gone = [[False for y in range(n)] for x in range(n)]
  en = [0 for _ in range(k)]
  for (y,x) in ts:
    gone[y][x] = True
   
  logs = []
  for _,(s,t) in dss:
    if uf.same(s,t):
      continue
    if en[s] >= 2 or en[t] >= 2:
      continue
    uf.union(s,t)
    en[s] += 1
    en[t] += 1
    
    ng = [[a for a in v] for v in gone]
    (sy,sx) = ts[s]
    bfs = [(0,0,[(sy,sx)],(sy,sx))]
    heapq.heapify(bfs)
    def search():
      # print(ts[s],ts[t])
      while len(bfs)>0:
        l,c,log,(y,x) = heapq.heappop(bfs)
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
          ty = y + dy
          tx = x + dx
          if ty<0 or tx<0 or n<=ty or n<=tx:
            continue
          if (ty,tx) == ts[t]:
            return log+[(ty,tx)]
          
          if ng[ty][tx]:
            continue
          
          ng[ty][tx] = True
          td = (l+1,c-A[ty][tx],log+[(ty,tx)],(ty,tx))
          heapq.heappush(bfs,td)
     
    v = search()
    if v is not None:
      for (y,x) in v:
        gone[y][x] = True
    # print(s,t,v)
    logs.append(v)
    
  
  src = None
  dst = None
  for i in range(k):
    if en[i] == 1:
      dst = src
      src = ts[i]
  
  # print(src,dst)
  
  if any(map(lambda v: v is None, logs)):
    return None
  
  p = src
  res = [src]
  while True:
    for i in range(len(logs)):
      if p in logs[i]:
        nl = logs[i]
        logs[i] = []
        if nl[-1]==p:
          nl = nl[::-1]
        assert(nl[0] == p)
        res += nl[1:]
        p = nl[-1]
    
    if p == dst:
      break
  
  # print(res)
  if len(res)<=T:
    return res
  return None
  # exit()
    
  
  
  # print(dss[:10],ts[3],ts[1])
  # exit()
  

def main():
  # return solve(5)
  l = 0
  r = T
  while (r-l>1):
    m = (l+r)//2
    # print(m)
    d = solve(m)
    if d is None:
      r = m
    else:
      l = m
  
  ans = solve(l)
  # print(l,ans)
  return ans

path = main()
if path == [None]:
  print(1)
  print(0,0)
else:
  print(len(path))
  for i, j in path:
      print(i, j)
0