結果
問題 | No.762 PDCAパス |
ユーザー | soraie_ |
提出日時 | 2021-03-24 09:32:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 5,679 bytes |
コンパイル時間 | 3,254 ms |
コンパイル使用メモリ | 238,912 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-05-05 02:26:26 |
合計ジャッジ時間 | 4,547 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 18 ms
5,376 KB |
testcase_23 | AC | 18 ms
5,376 KB |
testcase_24 | AC | 32 ms
8,576 KB |
testcase_25 | AC | 32 ms
8,576 KB |
testcase_26 | AC | 17 ms
5,376 KB |
testcase_27 | AC | 18 ms
5,376 KB |
testcase_28 | AC | 28 ms
7,168 KB |
testcase_29 | AC | 27 ms
7,168 KB |
testcase_30 | AC | 26 ms
6,272 KB |
testcase_31 | AC | 28 ms
6,400 KB |
testcase_32 | AC | 29 ms
6,272 KB |
testcase_33 | AC | 29 ms
5,504 KB |
testcase_34 | AC | 26 ms
5,504 KB |
testcase_35 | AC | 27 ms
5,504 KB |
testcase_36 | AC | 24 ms
5,376 KB |
testcase_37 | AC | 24 ms
5,376 KB |
testcase_38 | AC | 24 ms
5,376 KB |
testcase_39 | AC | 24 ms
5,376 KB |
testcase_40 | AC | 25 ms
5,376 KB |
ソースコード
#ifdef _DEBUG #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; //-------------------------------------------------------------------- #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define overload4(_1,_2,_3,_4,name,...) name #define rep1(n) for(ll _=0;_<(ll)n;++_) #define rep2(i,n) for(ll i=0;i<(ll)n;++i) #define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i) #define rep4(i,a,b,c) for(ll i=(ll)a;i<(ll)b;i+=(ll)c) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #ifdef _DEBUG #define pass(...) __VA_ARGS__ ; #define debug1(a) cerr<<#a<<": "<<a<<"\n" #define debug2(a,b) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" /* #define debug1(a) cout<<#a<<": "<<a<<"\n" #define debug2(a,b) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" */ #define debug(...) overload4(__VA_ARGS__,debug4,debug3,debug2,debug1)(__VA_ARGS__) #define koko cerr << "koko\n"; #else #define debug(...) void(0) #define pass(...) void(0); #define koko void(0); #endif #define mp make_pair //#define fi first //#define se second void myset(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} void doset(int n){cout << fixed << setprecision(n);cerr << fixed << setprecision(n);} using ll = long long; using ld = long double; using dou = double; template<class First,class Second>ostream& operator<<(ostream& os,const pair<First,Second>& pp) {return os << "{" << pp.first << "," << pp.second << "}";} template<class T>ostream& operator<<(ostream& os,const vector<T>& VV) {if(VV.empty())return os<<"[]";os<<"[";rep(i,VV.size())os<<VV[i]<<(i==int(VV.size()-1)?"]":",");return os;} template<class T>ostream& operator<<(ostream& os,const set<T>& SS) {if(SS.empty())return os<<"[]";os<<"[";auto ii=SS.begin();for(;ii!=SS.end();ii++)os<<*ii<<(ii==prev(SS.end())?"]":",");return os;} template<class Key,class Tp>ostream& operator<<(ostream& os,const map<Key,Tp>& MM) {if(MM.empty())return os<<"[]";os<<"[";auto ii=MM.begin();for(;ii!=MM.end();ii++)os<<"{"<<ii->first<<":"<<ii->second<<"}"<<(ii==prev(MM.end())?"]":",");return os;} const int inf = 1 << 30; const ll INF = 1LL << 61; const ld pi = 3.14159265358; const ll mod1 = 1000000007LL; const ll mod2 = 998244353LL; typedef pair<ll,ll> P; template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; } template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } ll modpow(ll n,ll m,ll MOD){ if(m == 0)return 1; if(m < 0)return 0; ll res = 1; n %= MOD; while(m){ if(m & 1)res = (res * n) % MOD; m >>= 1; n *= n; n %= MOD; } return res; } ll mypow(ll n,ll m){ if(m == 0)return 1; if(m < 0)return -1; ll res = 1; while(m){ if(m & 1)res = (res * n); m >>= 1; n *= n; } return res; } inline bool isp(ll n){ bool res = true; if(n == 1 || n == 0)return false; else{ for(ll i = 2;i * i <= n;i++){ if(n % i == 0){ res = false; break; } } return res; } } inline bool Yes(bool b = 1){cout << (b ? "Yes\n":"No\n");return b;} inline bool YES(bool b = 1){cout << (b ? "YES\n":"NO\n");return b;} map<ll,ll> primefactor(ll n){ map<ll,ll> ma; if(n <= 1)return ma; ll m = n; for(ll i = 2;i * i <= n;i++){ while(m % i == 0){ ma[i]++; m /= i; } } if(m != 1)ma[m]++; return ma; } vector<ll> divisor(ll n,bool sorted = true,bool samein = false){ vector<ll> res; for(ll i = 1;i * i <= n;i++){ if(n % i == 0){ res.push_back(i); if(i * i != n || samein)res.push_back(n / i); } } if(sorted)sort(all(res)); return res; } ll __lcm(ll a,ll b){return a / __gcd(a,b) * b;} template<class T>T sum(const vector<T> &V){T r=0;for(auto x:V)r+=x;return r;} template<class T>T sum(const initializer_list<T> &V){T r=0;for(auto x:V)r+=x;return r;} //#include <atcoder/all> //#include "atcoder/lazysegtree.hpp" //using namespace atcoder; //-------------------------------------------------------------------- #include "atcoder/modint.hpp" using mint = atcoder::modint1000000007; int N,M; string S; vector<vector<int>> G; vector<mint> memo; map<char,int> ord; int main(){ myset(); cin >> N >> M >> S; G.resize(N); memo.resize(N); ord['P'] = 0; ord['D'] = 1; ord['C'] = 2; ord['A'] = 3; rep(i,M){ int a,b; cin >> a >> b; a--;b--; if(ord[S[a]] > ord[S[b]])swap(a,b); if(ord[S[a]] + 1 == ord[S[b]]){ G[a].push_back(b); } } queue<int> que; vector<bool> use(N); rep(i,N)if(ord[S[i]] == 0){ que.push(i); memo[i] = 1; use[i] = true; } while(!que.empty()){ int p = que.front(); que.pop(); for(auto x : G[p]){ memo[x] += memo[p]; if(!use[x]){ que.push(x); use[x] = true; } } } mint ans = 0; rep(i,N){ ans += memo[i] * (ord[S[i]] == 3); } cout << ans.val() << "\n"; }