結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2019-03-26 04:55:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,018 bytes |
コンパイル時間 | 1,602 ms |
コンパイル使用メモリ | 173,208 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-10-11 00:17:12 |
合計ジャッジ時間 | 4,787 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include"bits/stdc++.h"using namespace std;using ll = long long;using ld = long double;using pii = pair<int, int>;using pll = pair<ll, ll>;#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)#define REP(i,n) FOR((i),0,(n))#define WAITING(str) int str;std::cin>>str;#define DEBUGING(str) cout<< #str << " " str<<endlconstexpr int INF = (1 << 30);constexpr ll INFL = (1ll << 60);constexpr ll MOD = 1000000007;// 10^9+7int main(){int N, M;string S;cin >> N >> M >> S;vector<ll> score(N);vector<vector<int>> edges(N);REP(i, M) {int a, b;cin >> a >> b;a--; b--;edges[a].push_back(b);edges[b].push_back(a);}ll res = 0;REP(from, N)if (S[from] == 'C')for (auto to : edges[from])if (S[to] == 'A')score[from]++;REP(from, N)if (S[from] == 'D')for (auto to : edges[from])if (S[to] == 'C')score[from] = (score[from] + score[to]) % MOD;REP(from, N)if (S[from] == 'P')for (auto to : edges[from])if (S[to] == 'D')res = (res + score[to]) % MOD;cout << res << endl;return 0;}