結果
問題 | No.762 PDCAパス |
ユーザー | mai |
提出日時 | 2018-11-17 13:25:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 4,063 bytes |
コンパイル時間 | 1,884 ms |
コンパイル使用メモリ | 205,932 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-06 20:35:14 |
合計ジャッジ時間 | 3,264 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 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 | 1 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 | 1 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 | 1 ms
5,376 KB |
testcase_22 | AC | 3 ms
5,376 KB |
testcase_23 | AC | 4 ms
5,376 KB |
testcase_24 | AC | 6 ms
5,376 KB |
testcase_25 | AC | 6 ms
5,376 KB |
testcase_26 | AC | 5 ms
5,376 KB |
testcase_27 | AC | 5 ms
5,376 KB |
testcase_28 | AC | 6 ms
5,376 KB |
testcase_29 | AC | 6 ms
5,376 KB |
testcase_30 | AC | 7 ms
5,376 KB |
testcase_31 | AC | 7 ms
5,376 KB |
testcase_32 | AC | 6 ms
5,376 KB |
testcase_33 | AC | 6 ms
5,376 KB |
testcase_34 | AC | 6 ms
5,376 KB |
testcase_35 | AC | 6 ms
5,376 KB |
testcase_36 | AC | 7 ms
5,376 KB |
testcase_37 | AC | 6 ms
5,376 KB |
testcase_38 | AC | 6 ms
5,376 KB |
testcase_39 | AC | 6 ms
5,376 KB |
testcase_40 | AC | 6 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #if defined(_WIN32) || defined(_WIN64) #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #elif defined(__GNUC__) #else #define getchar_unlocked getchar #define putchar_unlocked putchar #endif namespace { #define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template<typename T> void input_integer(T& var) noexcept { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'<cc; cc = getchar_unlocked()) if (cc == '-') sign = -1; for (; '0' <= cc && cc <= '9'; cc = getchar_unlocked()) var = (var << 3) + (var << 1) + cc - '0'; var = var * sign; } inline int c() noexcept { return getchar_unlocked(); } inline MaiScanner& operator>>(int& var) noexcept { input_integer<int>(var); return *this; } inline MaiScanner& operator>>(long long& var) noexcept { input_integer<long long>(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiblechar(cc); cc = getchar_unlocked()); for (; isvisiblechar(cc); cc = getchar_unlocked()) var.push_back(cc); return *this; } template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; } }; class MaiPrinter { public: template<typename T> void output_integer(T var) noexcept { if (var == 0) { putchar_unlocked('0'); return; } if (var < 0) putchar_unlocked('-'), var = -var; char stack[32]; int stack_p = 0; while (var) stack[stack_p++] = '0' + (var % 10), var /= 10; while (stack_p) putchar_unlocked(stack[--stack_p]); } inline MaiPrinter& operator<<(char c) noexcept { putchar_unlocked(c); return *this; } inline MaiPrinter& operator<<(int var) noexcept { output_integer<int>(var); return *this; } inline MaiPrinter& operator<<(long long var) noexcept { output_integer<long long>(var); return *this; } inline MaiPrinter& operator<<(char* str_p) noexcept { while (*str_p) putchar_unlocked(*(str_p++)); return *this; } inline MaiPrinter& operator<<(const string& str) { const char* p = str.c_str(); const char* l = p + str.size(); while (p < l) putchar_unlocked(*p++); return *this; } template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this <<* begin; } }; } MaiScanner scanner; MaiPrinter printer; // ============================================================================= using ll = long long; const ll MD = 1e9+7; int N, M; string label; int dp[100010]; vector<pair<int, int> > edge_pd, edge_dc, edge_ca; int main() { scanner >> N >> M >> label; for (int _ = M-1; 0 <= _; --_) { int a, b; char ca, cb; scanner >> a >> b; --a; --b; if (label[a] < label[b]) swap(a, b); // note: [A,C,D,P]を降順に並べるとPDCA ca = label[a]; cb = label[b]; if (ca == 'P' && cb == 'D') { edge_pd.emplace_back(a, b); dp[a] = 1; } else if (ca == 'D' && cb == 'C') { edge_dc.emplace_back(a, b); } else if (ca == 'C' && cb == 'A') { edge_ca.emplace_back(a, b); } } for (auto edge : edge_pd) { dp[edge.second] = (dp[edge.second] + dp[edge.first]) % MD; } for (auto edge : edge_dc) { dp[edge.second] = (dp[edge.second] + dp[edge.first]) % MD; } int answer = 0; for (auto edge : edge_ca) { answer = (answer + dp[edge.first]) % MD; } cout << answer << endl; return 0; }