結果
問題 | No.1898 Battle and Exchange |
ユーザー |
|
提出日時 | 2022-04-08 22:46:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,431 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 273,220 KB |
最終ジャッジ日時 | 2024-11-28 13:39:14 |
合計ジャッジ時間 | 77,336 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 TLE * 3 |
ソースコード
import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N,M = mi()edge = [[] for v in range(N)]for _ in range(M):u,v = mi()edge[u-1].append(v-1)edge[v-1].append(u-1)_card = []for i in range(N):a,b,c = mi()_card.append(sorted([a,b,c]))def cond(k):card = [[a for a in _card[v]] for v in range(N)]my_card = [1,1,k-2]if sum(card[0]) >= k:return Falseif my_card[0] < card[0][2]:my_card[0],card[0][2] = card[0][2],my_card[0]card[0].sort()my_card.sort()pq = [(-card[0][2],0)]visit = [False] * Nvisit[0] = Truef = Falsefor v in edge[0]:if sum(card[v]) < sum(my_card):f = Trueheappush(pq,(-card[v][2],v))visit[v] = Trueif not f:return Falsestrong = []for v in range(N):if visit[v]:for nv in edge[v]:if not visit[nv]:heappush(strong,(sum(card[nv]),nv))while True:#print(visit)#print(card)#print(my_card)#print(pq)change = Falsenew_v = Falseval,v = heappop(pq)val = -val#print(val,v)i = card[v].index(val)if val > my_card[0]:change = Truemy_card[0],card[v][i] = card[v][i],my_card[0]card[v].sort()my_card.sort()heappush(pq,(-card[v][2],v))while strong:val,nv = strong[0]if visit[nv]:heappop(strong)continueif val < sum(my_card):new_v = Trueheappop(strong)visit[nv] = Trueheappush(pq,(-card[nv][2],nv))for nnv in edge[nv]:if not visit[nnv]:heappush(strong,(sum(card[nnv]),nnv))else:breakif not change and not new_v:breakreturn visit[-1]ok = 10**9ng = 2while ok-ng>1:mid = (ok+ng)//2if cond(mid):ok = midelse:ng = midprint(1,1,ok-2)