結果
問題 | No.762 PDCAパス |
ユーザー |
|
提出日時 | 2023-05-10 00:08:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 900 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 90,452 KB |
最終ジャッジ日時 | 2024-11-26 08:36:36 |
合計ジャッジ時間 | 6,506 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
from collections import defaultdictn, m = map(int, input().split())s = input()G = defaultdict(list)for _ in range(m):u, v = map(int, input().split())u -= 1v -= 1if s[u] == 'P' and s[v] == 'D':G[v].append(u)elif s[u] == 'D' and s[v] == 'P':G[u].append(v)elif s[u] == 'D' and s[v] == 'C':G[v].append(u)elif s[v] == 'D' and s[u] == 'C':G[u].append(v)elif s[u] == 'C' and s[v] == 'A':G[v].append(u)elif s[u] == 'A' and s[v] == 'C':G[u].append(v)mod = 10**9 + 7DP = [0 for _ in range(n)]for ss in ['A', 'C', 'D']:for i in range(n):if s[i] == ss:if ss == 'A':DP[i] = 1for j in G[i]:DP[j] += DP[i]DP[j] %= modans = 0for i in range(n):if s[i] == 'P':ans += DP[i]ans %= modprint(ans)