結果
問題 | No.762 PDCAパス |
ユーザー |
|
提出日時 | 2019-09-12 21:18:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,028 bytes |
コンパイル時間 | 1,886 ms |
コンパイル使用メモリ | 174,884 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2024-07-02 17:10:45 |
合計ジャッジ時間 | 5,041 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;int n, m;string s;vector<int> g[(int)1e5];long long mod = 1e9 + 7;int x[(int)1e5];string pdca = "PDCA";long long dfs(int cur) {long long ret = 0;if (s[cur] == 'A') {return 1;}for (int to: g[cur]) {if (x[to] == -1) {ret += dfs(to);} else {ret += x[to];}ret %= mod;}x[cur] = ret;return ret;}int main() {cin>>n>>m;cin>>s;set<int> ps;for (int i=0; i<m; i++) {int u, v;cin>>u>>v;--u;--v;int iu = pdca.find(s[u]);int iv = pdca.find(s[v]);if (iu == string::npos || iv == string::npos) {continue;}if (iv == iu + 1) {g[u].push_back(v);if (s[u] == 'P') {ps.insert(u);}} else if (iu == iv + 1) {g[v].push_back(u);if (s[v] == 'P') {ps.insert(v);}}}for (int i=0; i<n; i++) x[i] = -1;long long ans = 0;for (int i: ps) {ans += dfs(i);ans %= mod;}cout<<ans<<endl;}