fork download
copy 
  1. /*
  2.  * Language: Standard C++23 [-std=c++23]
  3.  * Author: Zang Vũ aka zvwgvx
  4.  * Github & Discord & Facebook: @zvwgvx
  5.  */
  6.  
  7. #pragma GCC optimize("fast-math,O3")
  8. #pragma GCC optimize("no-stack-protector") 
  9. #pragma GCC optimize("unroll-loops")
  10. // #pragma GCC optimize("Ofast")
  11. // #pragma GCC target("tune=native")
  12. // #pragma GCC target("avx,avx2,fma")
  13.  
  14. #include <bits/stdc++.h>
  15.  
  16. using namespace std;
  17.  
  18. #define ENV defined(LOCAL)
  19. #define el cout << '\n'
  20. #define rt return
  21. #define ll long long
  22. #define ull unsigned ll
  23. #define pii pair <int, int>
  24. #define pll pair <ll, ll>
  25. #define vi vector <int>
  26. #define vl vector <ll>
  27. #define vc vector <char>
  28. #define vvi vector <vector <int>>
  29. #define vvl vector <vector <ll>>
  30. #define mts multiset
  31. #define mtm multimap
  32. #define ump unordered_map
  33. #define ust unordered_set
  34. #define umts unordered_multiset
  35. #define umtm unordered_multimap
  36. #define priq priority_queue
  37.  
  38. template <typename T>
  39. T fgcd(T a, T b) {
  40.     if (!a || !b) rt a | b;
  41.     unsigned shift = __builtin_ctzll(a | b);
  42.     a >>= __builtin_ctzll(a);
  43.     while (b) {
  44.         b >>= __builtin_ctzll(b);
  45.         if (a > b) swap(a, b);
  46.         b -= a;
  47.     }
  48.     rt a << shift;
  49. }
  50.  
  51. template <typename T>
  52. T fpow(T base, T exp, T mod) {
  53.     T res = 1;
  54.     for (; exp; exp >>= 1, base = base * base % mod)
  55.         if (exp & 1) res = res * base % mod;
  56.     return res;
  57. }
  58.  
  59. template <typename T> T lcm(T a, T b) { rt a * (b / fgcd(a, b)); }
  60. template <typename T> void maximize(T& a, T b) { if (a < b) a = b; }
  61. template <typename T> void minimize(T& a, T b) { if (a > b) a = b; }
  62. template <typename T> double lg(T a, T b) { rt log(b) / log(a); }
  63. template <typename T> ull P(T n, T k) { ull res = 1; for (int i = 0; i < k; i++) res *= (n - i); rt res; }
  64. template <typename T> ull C(T n, T k) { ull res = 1; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; rt res; }
  65.  
  66. const int MOD = 1e9 + 7;
  67. const int INF = 1e9;
  68. const int LIMIT = 1e6 + 5;
  69.  
  70. #if ENV
  71. void open(const string& file) {
  72.     freopen((file + ".inp").c_str(), "r", stdin);
  73.     freopen((file + ".out").c_str(), "w", stdout);
  74. }
  75. auto start = clock();
  76. void time() { cout << "\n\n[rt] " << 1.0 * (clock() - start) / CLOCKS_PER_SEC; }
  77. #endif
  78.  
  79. signed main() { 
  80.     cin.tie(nullptr), cout.tie(nullptr)
  81.     -> ios_base::sync_with_stdio(false);
  82.  
  83.     #if ENV 
  84.         open("main");
  85.         srand(time(nullptr));
  86.     #endif
  87.  
  88.     int N, K;
  89.     cin >> N >> K;
  90.  
  91.     string S, T;
  92.     cin >> S >> T;
  93.  
  94.     vector<string> w;
  95.     w.push_back(S);
  96.     w.push_back(T);
  97.     for (int i = 0; i < N; i++){
  98.         string tmp;
  99.         cin >> tmp;
  100.         w.push_back(tmp);
  101.     }
  102.     int total = w.size();
  103.  
  104.     ump<string, vi> table;
  105.     table.reserve(total * 2);
  106.     for (int i = 0; i < total; i++){
  107.         table[w[i]].push_back(i);
  108.     }
  109.  
  110.     vvi g(total);
  111.     for (int i = 0; i < total; i++){
  112.         string cur = w[i];
  113.         for (int pos = 0; pos < K; pos++){
  114.             char orig = cur[pos];
  115.             for (char c = 'a'; c <= 'z'; c++){
  116.                 if (c == orig) continue;
  117.                 cur[pos] = c;
  118.                 if (table.find(cur) != table.end()){
  119.                     for (int idx : table[cur]){
  120.                         g[i].push_back(idx);
  121.                     }
  122.                 }
  123.             }
  124.             cur[pos] = orig;
  125.         }
  126.     }
  127.  
  128.     vi dist(total, INF);
  129.     vl dp(total, 0);
  130.     deque<int> dq;
  131.  
  132.     dist[0] = 0;
  133.     dp[0] = 1;
  134.     dq.push_back(0);
  135.  
  136.     while (!dq.empty()){
  137.         int u = dq.front();
  138.         dq.pop_front();
  139.         int d = dist[u];
  140.         for (int v : g[u]){
  141.             if (dist[v] > d + 1){
  142.                 dist[v] = d + 1;
  143.                 dp[v] = dp[u];
  144.                 dq.push_back(v);
  145.             }
  146.             else if (dist[v] == d + 1){
  147.                 dp[v] = (dp[v] + dp[u]) % MOD;
  148.             }
  149.         }
  150.     }
  151.  
  152.     if (S == T) {
  153.         cout << "0 1";
  154.     } else if (dist[1] == INF) {
  155.         cout << "-1 -1";
  156.     } else {
  157.         cout << dist[1] << " " << dp[1] % MOD;
  158.     }
  159.  
  160.     #if ENV 
  161.         time();
  162.     #endif
  163.  
  164.     rt 0;   
  165. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
https://ideone.com/vEN4OK
language:
C++14 (clang 8.0)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!