結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:40:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,091 bytes |
コンパイル時間 | 1,016 ms |
コンパイル使用メモリ | 81,548 KB |
実行使用メモリ | 133,800 KB |
最終ジャッジ日時 | 2023-10-19 12:12:43 |
合計ジャッジ時間 | 17,751 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 99 ms
79,912 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 231 ms
94,940 KB |
testcase_24 | AC | 170 ms
88,756 KB |
testcase_25 | AC | 328 ms
100,028 KB |
testcase_26 | AC | 431 ms
108,324 KB |
testcase_27 | AC | 330 ms
100,716 KB |
testcase_28 | AC | 266 ms
94,564 KB |
testcase_29 | AC | 318 ms
100,712 KB |
testcase_30 | AC | 273 ms
95,940 KB |
testcase_31 | AC | 252 ms
95,260 KB |
testcase_32 | AC | 269 ms
99,008 KB |
testcase_33 | AC | 433 ms
106,384 KB |
testcase_34 | AC | 436 ms
106,228 KB |
testcase_35 | AC | 437 ms
115,512 KB |
testcase_36 | AC | 420 ms
111,344 KB |
testcase_37 | AC | 236 ms
99,296 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 247 ms
126,668 KB |
testcase_45 | AC | 197 ms
98,464 KB |
testcase_46 | AC | 148 ms
110,484 KB |
testcase_47 | AC | 96 ms
79,960 KB |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heappush, heappop, heapify import math import bisect import random from itertools import permutations, accumulate, combinations, product import sys import string from bisect import bisect_left, bisect_right from math import factorial, ceil, floor from operator import mul from functools import reduce import pprint sys.setrecursionlimit(10 ** 9) INF = 10 ** 20 def LI(): return list(map(int, sys.stdin.readline().split())) def I(): return int(sys.stdin.readline()) def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split() def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8') def IR(n): return [I() for i in range(n)] def LIR(n): return [LI() for i in range(n)] def SR(n): return [S() for i in range(n)] def LSR(n): return [LS() for i in range(n)] def SRL(n): return [list(S()) for i in range(n)] def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)] mod = 10**9+7 n,m=LI() G=[[]for _ in range(n+1)] for _ in range(m): u,v,l,a=LI() G[u]+=[(v,l,a)] def topological_sort(G): n = len(G) in_degree = [0] * n for u in range(n): for v,_,_ in G[u]: in_degree[v] += 1 topological_order = [] que = deque() for i in range(n): if in_degree[i] == 0: que += [i] while que: u = que.pop() topological_order += [u] for v,_,_ in G[u]: in_degree[v] -= 1 if in_degree[v] == 0: que += [v] return topological_order q=deque([0]) D=[0]*(n+1) D2=[0]*(n+1) D2[0]=1 D[0]=0 order=topological_sort(G) s=set() for ui in order: s.add(ui) for vi,li,ai in G[ui]: if vi in s: print("INF") exit() D[vi]+=(D[ui]+D2[ui]*li)*ai%mod D2[vi]+=D2[ui]*ai D2[vi]%=mod qq=[0] D3=[0]*(n+1) D3[0]=1 while qq: uk=qq.pop() for vk,_,_ in G[uk]: if D3[vk]: continue D3[vk]=1 qq+=[vk] if not D2[n] and D3[n]: print("INF") else: print(D2[n])