結果
問題 | No.762 PDCAパス |
ユーザー |
|
提出日時 | 2018-12-10 11:54:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 1,085 ms |
コンパイル使用メモリ | 65,456 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-09-16 15:47:54 |
合計ジャッジ時間 | 3,803 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream> #include <vector> #include <string.h> using namespace std; string S; vector<vector<int>> roads; long dp[100010][3]; long move(int now, int PDCA){ if(PDCA == 3){ return 1; }else if(dp[now][PDCA] != -1){ return dp[now][PDCA]; } long ans = 0; for(int i: roads[now]){ if(S[i] == "PDCA"[PDCA + 1]){ ans += move(i, PDCA + 1); } } return dp[now][PDCA] = ans % long(1e9 + 7); } int main(){ int N, M; cin >> N >> M >> S; roads.resize(N); for(int i = 0; i < M; i++){ int u, v; cin >> u >> v; roads[u - 1].push_back(v - 1); roads[v - 1].push_back(u - 1); } memset(dp, -1, sizeof(dp)); long ans = 0; for(int i = 0; i < N; i++){ if(S[i] == 'P'){ ans += move(i, 0); } } cout << ans % long(1e9 + 7) << endl; }