結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2019-06-17 09:03:19 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 3,091 bytes |
コンパイル時間 | 909 ms |
コンパイル使用メモリ | 105,668 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-11-26 11:17:24 |
合計ジャッジ時間 | 4,088 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <vector>#include <list>#include <map>#include <set>#include <unordered_set>#include <unordered_map>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <queue>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <ctime>#include <fstream>#include <cstdio>#include <climits>#include <complex>#include <cstdint>#include <tuple>#define M_PI 3.14159265358979323846using namespace std;//conversion//------------------------------------------inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }inline int readInt() { int x; scanf("%d", &x); return x; }//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a)*(a))#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define EXIST(s,e) ((s).find(e)!=(s).end())#define SORT(c) sort((c).begin(),(c).end())//repetition//------------------------------------------#define FOR(i,s,n) for(int i=s;i<(int)n;++i)#define REP(i,n) FOR(i,0,n)#define MOD 1000000007#define rep(i, a, b) for(int i = a; i < (b); ++i)#define trav(a, x) for(auto& a : x)#define all(x) x.begin(), x.end()#define sz(x) (int)(x).size()struct Edge {int to, cost;Edge(int to, int cost): to(to), cost(cost) {}};typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<vector<Edge>> AdjList;AdjList graph;const int INF = 100000000;LL N, M;int h[155];vector<vector<int>> P(100010);LL dp[100010];int main() {//cout << fixed << setprecision(15);cin >> N >> M;string S; cin >> S;vector<pair<int, int>> path_pd, path_dc, path_ca;REP(i, M){int u, v; cin >> u >> v;u--;v--;if(S[u] < S[v]) swap(u, v);if(S[u]=='P' && S[v] == 'D'){dp[u] = 1;path_pd.emplace_back(u, v);}else if(S[u] == 'D' && S[v] == 'C'){path_dc.emplace_back(u, v);}else if(S[u] =='C' && S[v] == 'A') {path_ca.emplace_back(u, v);}}for(auto e: path_pd){dp[e.second] = (dp[e.second] + dp[e.first])%MOD;}for(auto e: path_dc){dp[e.second] = (dp[e.second] + dp[e.first])%MOD;}int ans=0;for(auto e: path_ca){ans = (ans + dp[e.first])%MOD;}cout << ans << endl;return 0;}