結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-20 04:48:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 858 ms / 2,500 ms |
コード長 | 2,246 bytes |
コンパイル時間 | 814 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 188,452 KB |
最終ジャッジ日時 | 2024-12-29 09:00:54 |
合計ジャッジ時間 | 21,497 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#SCC参考元:https://judge.yosupo.jp/submission/22487def scc(E):n = len(E)iE = [[] for _ in range(n)]for i, e in enumerate(E):for v in e:iE[v].append(i)T = []done = [0] * n # 0 -> 1 -> 2ct = 0for i0 in range(n):if done[i0]: continueQ = [~i0, i0]while Q:i = Q.pop()if i < 0:if done[~i] == 2: continuedone[~i] = 2T.append(~i)ct += 1continueif i >= 0:if done[i]: continuedone[i] = 1for j in E[i]:if done[j]: continueQ.append(~j)Q.append(j)done = [0] * nSCC = []for i0 in T[::-1]:if done[i0]: continueL = []Q = [~i0, i0]while Q:i = Q.pop()if i < 0:if done[~i] == 2: continuedone[~i] = 2L.append(~i)continueif i >= 0:if done[i]: continuedone[i] = 1for j in iE[i]:if done[j]: continueQ.append(~j)Q.append(j)SCC.append(L)return SCC#================================================from collections import defaultdictN,M=map(int,input().split())Mod=10**9+7X=[[] for _ in range(N+1)]E=[defaultdict(lambda :[0,0]) for _ in range(N+1)]for _ in range(M):u,v,w,a=map(int,input().split())X[u].append(v)b,l=E[u][v]E[u][v]=[b+a,(l+a*w)%Mod]S=scc(X)inf=float("inf")Flag=[0]*(N+1)Flag[0]=1DP=[[0,0] for _ in range(N+1)]DP[0]=[1,0]for U in S:if len(U)>=2:F=0for v in U:F|=Flag[v]if F:for v in U:DP[v]=[inf,inf]for u in U:x,y=DP[u]for v in E[u]:Flag[v]|=Flag[u]if x==inf:DP[v]=[inf,inf]else:a,w=E[u][v]DP[v][0]+=x*aDP[v][1]+=y*a+x*wDP[v][0]%=ModDP[v][1]%=Modprint(DP[N][1] if DP[N][1]<inf else "INF")