結果
問題 | No.762 PDCAパス |
ユーザー |
|
提出日時 | 2019-08-21 16:24:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 752 bytes |
コンパイル時間 | 2,009 ms |
コンパイル使用メモリ | 196,472 KB |
最終ジャッジ日時 | 2025-01-07 14:34:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;int main() {int n,m;cin>>n>>m;string s;cin>>s;vector<int> g[n];ll dp[n]{};for (int i=0;i<m;i++) {int v,u;cin>>v>>u;v--,u--;if (s[v]=='P') dp[v]=1;if (s[u]=='P') dp[u]=1;g[v].push_back(u);g[u].push_back(v);}string pdca="PDCA";ll ans=0;int mod=1e9+7;for (int i=0;i<3;i++)for (int j=0;j<n;j++)if (s[j]==pdca[i])for (int u:g[j])if (s[u]==pdca[i+1]) {if (i==2) ans=(ans+dp[j])%mod;else dp[u]=(dp[u]+dp[j])%mod;}cout<<ans<<endl;return 0;}