結果
問題 | No.762 PDCAパス |
ユーザー | Shuz* |
提出日時 | 2018-12-10 08:46:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 3,934 bytes |
コンパイル時間 | 1,953 ms |
コンパイル使用メモリ | 175,560 KB |
実行使用メモリ | 12,840 KB |
最終ジャッジ日時 | 2024-09-16 15:46:52 |
合計ジャッジ時間 | 3,884 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 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 | 18 ms
5,376 KB |
testcase_23 | AC | 18 ms
5,376 KB |
testcase_24 | AC | 42 ms
12,448 KB |
testcase_25 | AC | 39 ms
12,320 KB |
testcase_26 | AC | 19 ms
5,376 KB |
testcase_27 | AC | 19 ms
5,376 KB |
testcase_28 | AC | 48 ms
12,584 KB |
testcase_29 | AC | 47 ms
12,840 KB |
testcase_30 | AC | 43 ms
11,144 KB |
testcase_31 | AC | 42 ms
11,148 KB |
testcase_32 | AC | 43 ms
11,144 KB |
testcase_33 | AC | 38 ms
9,432 KB |
testcase_34 | AC | 39 ms
9,304 KB |
testcase_35 | AC | 40 ms
9,300 KB |
testcase_36 | AC | 32 ms
6,752 KB |
testcase_37 | AC | 32 ms
6,728 KB |
testcase_38 | AC | 33 ms
6,736 KB |
testcase_39 | AC | 30 ms
6,872 KB |
testcase_40 | AC | 30 ms
6,852 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; //#include <boost/multiprecision/cpp_int.hpp> // using namespace boost::multiprecision; // using cint = cpp_int; //#pragma GCC optimize("", on) //#pragma GCC optimization_level 3 //#define min(...) min({...}) //#define max(...) max({...}) // Define using ll = long long; using ull = unsigned long long; using ld = long double; const ll dx[4] = {1, 0, -1, 0}; const ll dy[4] = {0, 1, 0, -1}; const ll MOD = 1e9 + 7; const ll inf = 1 << 30; const ll INF = LONG_MAX; const ull MAX = ULONG_MAX; #define mp make_pair #define pb push_back #define eb emplace_back #define x first #define y second #define endl '\n' #define space ' ' #define def inline auto #define func inline constexpr ll #define run __attribute__((constructor)) def _ #define all(v) begin(v), end(v) #define input(a) scanf("%lld", &(a)) #define print(a) printf("%lld\n", (a)) #define ok(a, b) (0 <= (a) && (a) < b) // Debug #define debug(...) \ { \ cerr << __LINE__ << ": " << #__VA_ARGS__ << " = "; \ for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] "; \ cerr << endl; \ } #define dump(a, h, w) \ { \ cerr << __LINE__ << ": " << #a << " = [" << endl; \ rep(__i, h) { \ rep(__j, w) cerr << a[__i][__j] << space; \ cerr << endl; \ } \ cerr << "]" << endl; \ } #define vdump(a, n) \ { \ cerr << __LINE__ << ": " << #a << " = ["; \ rep(__i, n) if (__i) cerr << space << a[__i]; \ else cerr << a[__i]; \ cerr << "]" << endl; \ } // Loop #define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i) #define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i) #define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i) #define each(i, a) for (auto &&i : a) #define loop() for (;;) // Stream #define fout(n) cout << fixed << setprecision(n) #define fasten cin.tie(0), ios::sync_with_stdio(0) // Speed run() { fasten, fout(10); } #pragma GCC optimize("O3") #pragma GCC target("avx") // Math func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } func lcm(ll a, ll b) { return a * b / gcd(a, b); } func sign(ll a) { return a ? abs(a) / a : 0; } def in() { ll A; cin >> A; return A; } ll N, M, A, B; string S; vector<vector<ll>> v; ll mem[100001][4]; def DFS (ll pos, ll depth) { string s = "PDCA"; ll res = 0; if (depth == 4) return 1LL; if (mem[pos][depth] != -1) return mem[pos][depth]; rep(i, v[pos].size()) { if(S[v[pos][i] - 1] == s[depth]) { res += DFS(v[pos][i], depth + 1); res %= MOD; } } return mem[pos][depth] = res; } signed main() { cin >> N >> M >> S; rep(i, N + 1) v.pb({}); rep(i, M) { cin >> A >> B; v[A].pb(B); v[B].pb(A); } rep(i, N + 1) rep(j, 4) mem[i][j] = -1; rep(i, N) if (S[i] == 'P') v[0].pb(i + 1); cout << DFS(0, 0) << endl; } // for compilation: g++ -Ofast -march=native -o _ _.cpp -std=c++17