結果
問題 | No.762 PDCAパス |
ユーザー |
|
提出日時 | 2022-02-12 22:51:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,047 bytes |
コンパイル時間 | 3,410 ms |
コンパイル使用メモリ | 234,176 KB |
実行使用メモリ | 14,336 KB |
最終ジャッジ日時 | 2024-06-29 02:04:17 |
合計ジャッジ時間 | 6,608 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using ll=long long;int main(){ll mod=1e9+7;int N,M;string S;cin>>N>>M>>S;vector<vector<int>> G(N);for(int i=0;i<M;i++){int u,v;cin>>u>>v;u--,v--;G[u].push_back(v);G[v].push_back(u);}vector<vector<ll>> dp(N,vector<ll>(3,0));for(int i=0;i<N;i++){for(int j:G[i]){if(S[i]=='P'&&S[j]=='D'){dp[j][0]++;}}}for(int i=0;i<N;i++){for(int j:G[i]){if(S[i]=='D'&&S[j]=='C'){dp[j][1]+=dp[i][0];dp[j][1]%=mod;}}}for(int i=0;i<N;i++){for(int j:G[i]){if(S[i]=='C'&&S[j]=='A'){dp[j][2]+=dp[i][1];dp[j][2]%=mod;}}}ll ans=0;for(int i=0;i<N;i++){ans+=dp[i][2];ans%=mod;}cout<<ans<<endl;return 0;}