結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2019-03-26 11:53:26 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,143 bytes |
コンパイル時間 | 1,511 ms |
コンパイル使用メモリ | 164,460 KB |
実行使用メモリ | 5,860 KB |
最終ジャッジ日時 | 2024-10-11 01:17:14 |
合計ジャッジ時間 | 4,018 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)#define all(x) (x).begin(),(x).end()#define pb push_backtemplate<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<vi> vvi;const int inf = 1LL<<60;const int mod = 1e9 + 7;const double eps = 1e-9;/*{}*/signed main(){int n, m;string s;cin >> n >> m >> s;vector<pii> pd, dc, ca;vi dp(n);rep(i, 0, m){int a, b;cin >> a >> b;a--; b--;if(s[a] < s[b]) swap(a, b);if(s[a] == 'P' and s[b] == 'D'){pd.pb({a, b});dp[a] = 1;}else if(s[a] == 'D' and s[b] == 'C'){dc.pb({a, b});}else if(s[a] == 'C' and s[b] == 'A'){ca.pb({a, b});}}for(auto e : pd){(dp[e.second] += dp[e.first]) %= mod;}for(auto e : dc){(dp[e.second] += dp[e.first]) %= mod;}int ans = 0;for(auto e : ca){(ans += dp[e.first]) %= mod;}cout << ans << endl;return 0;}