結果
問題 | No.762 PDCAパス |
ユーザー | tatyam |
提出日時 | 2018-12-10 09:00:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 4,800 bytes |
コンパイル時間 | 3,280 ms |
コンパイル使用メモリ | 217,520 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-09-16 15:47:28 |
合計ジャッジ時間 | 4,356 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 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 | 1 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 | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 17 ms
5,376 KB |
testcase_23 | AC | 19 ms
5,376 KB |
testcase_24 | AC | 27 ms
8,832 KB |
testcase_25 | AC | 26 ms
8,704 KB |
testcase_26 | AC | 17 ms
5,376 KB |
testcase_27 | AC | 17 ms
5,376 KB |
testcase_28 | AC | 29 ms
7,424 KB |
testcase_29 | AC | 32 ms
7,296 KB |
testcase_30 | AC | 30 ms
6,400 KB |
testcase_31 | AC | 29 ms
6,528 KB |
testcase_32 | AC | 29 ms
6,400 KB |
testcase_33 | AC | 25 ms
5,632 KB |
testcase_34 | AC | 24 ms
5,632 KB |
testcase_35 | AC | 25 ms
5,632 KB |
testcase_36 | AC | 25 ms
5,376 KB |
testcase_37 | AC | 23 ms
5,376 KB |
testcase_38 | AC | 22 ms
5,376 KB |
testcase_39 | AC | 22 ms
5,376 KB |
testcase_40 | AC | 24 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using namespace std::chrono; typedef long long ll; typedef pair<int,int> pii; typedef pair<double,double> pdd; #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) _rep2(i,n) #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(ll i=a;i<b;++i) #define _rep4(i,a,b,c) for(ll i=a;i<b;i+=c) #define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__) #define _rrep1(n) _rrep2(i,n) #define _rrep2(i,n) _rrep3(i,0,n) #define _rrep3(i,a,b) for(ll i=b-1;i>=a;i--) #define _rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) #define each(i,a) for(auto&& i:a) #define sum(...) accumulate(range(__VA_ARGS__),0LL) #define _range(i) (i).begin(),(i).end() #define _range2(i,k) (i).begin(),(i).begin()+k #define _range3(i,a,b) (i).begin()+a,(i).begin()+b #define range(...) _overload3(__VA_ARGS__,_range3,_range2,_range)(__VA_ARGS__) const ll LINF=0x3fffffffffffffff; const ll MOD=1000000007; const ll MODD=0x3b800001; const int INF=0x3fffffff; const vector<pii> four={{0,1},{1,0},{0,-1},{-1,0}}; #define yes(i) out(i?"yes":"no") #define Yes(i) out(i?"Yes":"No") #define YES(i) out(i?"YES":"NO") #define Possible(i)out(i?"Possible":"Impossible") #define unless(a) if(!(a)) #define elif else if //#define START auto start=system_clock::now() //#define END auto end=system_clock::now();cerr<<duration_cast<milliseconds>(end-start).count()<<" ms\n" #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define vec(type,name,...) vector<type> name(__VA_ARGS__); #define VEC(type,name,size) vector<type> name(size);in(name) #define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__)) #define pll pair<ll,ll> struct SETTINGS{SETTINGS(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}SETTINGS; template<typename T> inline bool update_min(T& mn,const T& cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;} template<typename T> inline bool update_max(T& mx,const T& cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;} template<typename T> inline T min(vector<T>& vec){return *min_element(range(vec));} template<typename T> inline T max(vector<T>& vec){return *max_element(range(vec));} template<typename T> inline constexpr T gcd (T a,T b) {if(a==b)return a;else return gcd(b,(a-1)%b+1);} inline constexpr ll POW(ll a,ll b){if(b==1)return a;ll ans=POW(a,b/2);ans*=ans;if(b&1)ans*=a;return ans;} inline constexpr ll MODPOW(ll a,ll b,ll mod){if(a>=mod)a%=mod;if(b==1)return a;ll ans=MODPOW(a,b/2,mod);ans*=ans;ans%=mod;if(b&1){ans*=a;ans%=mod;}return ans;} inline void in() {} template<typename T> istream& operator >> (istream& is, vector<T>& vec); template<typename T,size_t size> istream& operator >> (istream& is, array<T,size>& vec); template<typename T,typename L> istream& operator >> (istream& is, pair<T,L>& p); template<typename T> ostream& operator << (ostream& os, vector<T>& vec); template<typename T,typename L> ostream& operator << (ostream& os, pair<T,L>& p); template<typename T> istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;} template<typename T,typename L> istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;} template<typename T> ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;} template<typename T> ostream& operator << (ostream& os, deque<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;} template<typename T,typename L> ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;} template <class Head, class... Tail> inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);} template <typename T> inline void out(T t){cout<<t<<endl;} inline void out(){cout<<'\n';} template <class Head, class... Tail> inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);} signed main(){ LL(n,m); STR(s); vec(vector<ll>,d,n); map<char,ll>to_i; to_i['P']=0; to_i['D']=1; to_i['C']=2; to_i['A']=3; vec(ll,cnt,n); rep(m){ LL(a,b); a--; b--; if(to_i[s[a]]-to_i[s[b]]==1)d[b].push_back(a); elif(to_i[s[b]]-to_i[s[a]]==1)d[a].push_back(b); } rep(n)if(s[i]=='C')cnt[i]=d[i].size(); rep(n)if(s[i]=='D')each(j,d[i])cnt[i]=(cnt[i]+cnt[j])%MOD; ll ans=0; rep(n)if(s[i]=='P')each(j,d[i])ans=(ans+cnt[j])%MOD; out(ans); }