結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:44:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,882 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 133,632 KB |
最終ジャッジ日時 | 2024-09-19 08:21:17 |
合計ジャッジ時間 | 15,699 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 88 ms
80,512 KB |
testcase_01 | AC | 90 ms
80,640 KB |
testcase_02 | AC | 89 ms
80,512 KB |
testcase_03 | AC | 90 ms
80,640 KB |
testcase_04 | AC | 89 ms
80,512 KB |
testcase_05 | AC | 92 ms
80,640 KB |
testcase_06 | AC | 98 ms
80,768 KB |
testcase_07 | AC | 95 ms
80,384 KB |
testcase_08 | AC | 132 ms
84,352 KB |
testcase_09 | AC | 113 ms
81,920 KB |
testcase_10 | AC | 133 ms
83,584 KB |
testcase_11 | AC | 133 ms
84,056 KB |
testcase_12 | AC | 127 ms
83,712 KB |
testcase_13 | AC | 404 ms
118,656 KB |
testcase_14 | AC | 471 ms
117,760 KB |
testcase_15 | AC | 479 ms
123,520 KB |
testcase_16 | AC | 366 ms
108,496 KB |
testcase_17 | AC | 242 ms
108,672 KB |
testcase_18 | AC | 522 ms
131,200 KB |
testcase_19 | AC | 578 ms
133,632 KB |
testcase_20 | AC | 565 ms
133,592 KB |
testcase_21 | AC | 575 ms
131,240 KB |
testcase_22 | AC | 551 ms
131,200 KB |
testcase_23 | AC | 187 ms
92,160 KB |
testcase_24 | AC | 178 ms
89,164 KB |
testcase_25 | AC | 249 ms
99,456 KB |
testcase_26 | AC | 339 ms
108,416 KB |
testcase_27 | AC | 280 ms
101,248 KB |
testcase_28 | AC | 204 ms
94,848 KB |
testcase_29 | AC | 262 ms
100,992 KB |
testcase_30 | AC | 207 ms
94,608 KB |
testcase_31 | AC | 184 ms
93,440 KB |
testcase_32 | AC | 223 ms
96,896 KB |
testcase_33 | AC | 331 ms
104,960 KB |
testcase_34 | AC | 327 ms
105,728 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 224 ms
99,996 KB |
testcase_38 | AC | 281 ms
112,316 KB |
testcase_39 | AC | 281 ms
112,384 KB |
testcase_40 | AC | 286 ms
112,624 KB |
testcase_41 | AC | 278 ms
112,128 KB |
testcase_42 | AC | 279 ms
112,480 KB |
testcase_43 | AC | 213 ms
115,968 KB |
testcase_44 | AC | 222 ms
119,424 KB |
testcase_45 | AC | 198 ms
98,176 KB |
testcase_46 | AC | 138 ms
110,128 KB |
testcase_47 | WA | - |
ソースコード
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) if len(order)!=n+1: print("INF") exit() s=set() for ui in order: s.add(ui) for vi,li,ai in G[ui]: D[vi]+=(D[ui]+D2[ui]*li)*ai%mod D[vi]%=mod D2[vi]+=D2[ui]*ai D2[vi]%=mod print(D[n])