fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //typeDef
  6. typedef long long           lli;
  7. typedef long                li;
  8. typedef vector<int>         vi;
  9. typedef vector<li>          vli;
  10. typedef vector<lli>         vlli;
  11. typedef map<int, int>       mii;
  12. typedef set<int>            seti;
  13. typedef queue<int>          qi;
  14. typedef deque<int>          dqi;
  15. typedef stack<int>          stacki;
  16. typedef multiset<int>       mseti;
  17.  
  18. //loop
  19. #define rep(i, n)         for(int i = 0; i < n; ++i)
  20. #define fori(i, a, b)     for(int i = a; i <= b; ++i)
  21. #define ifor(i, a, b)     for(int i = a; i >= b; --i)
  22.  
  23. //Pair
  24. #define mp                  make_pair
  25. #define iPair               pair<int, int>
  26. #define lliPair             pair<lli, lli>
  27.  
  28. //Extras
  29. #define mod1                    1e9 + 7
  30. #define mod2                    1e9 + 9
  31. #define inf                     int(1e9)
  32. #define INF                     lli(1e18)
  33. #define pi                      3.14159265358979
  34. #define pb                      push_back
  35. #define pf                      push_front
  36. #define popb                    pop_back()
  37. #define popf                    pop_front()
  38. #define ff                      first
  39. #define ss                      second
  40. #define all(v)                  v.begin(), v.end()
  41. #define iter(container, it)     for(auto it = container.begin(); it != container.end(); ++it)
  42.  
  43. //functions
  44. lli gcd(lli a, lli b) { return (a == 0) ? b : gcd(b % a, a); }
  45. lli lcm(lli a, lli b) { return a / gcd(a, b) * b; }
  46.  
  47. int main()
  48. {
  49.      ios_base::sync_with_stdio(0);
  50.      cin.tie(0);
  51.  
  52.      int t;
  53.      cin >> t;
  54.      while (t--){
  55.           int i = 0;
  56.           map< char, vector<int> > alpha;
  57.           string s;
  58.  
  59.           cin >> s;
  60.           rep (i, s.size()){
  61.                alpha[s[i]].pb(i);
  62.                //as we know we can go to either next checkpoint or any other with the same ASCII value
  63.                //so inserting next checkpoint and similar checkpoint
  64.                if (i != s.size() - 1){
  65.                		//we can't push i = n (out of bound)
  66.                     alpha[s[i]].pb(i+1);
  67.                }
  68.           }
  69.  
  70.           int dist[s.size()] ;
  71.           fill_n(dist, s.size(), inf);
  72.           //source cost = 0
  73.           dist[0] = 0;
  74.           bool marked[26] = {false};
  75.  
  76. 		  //similar to bfs traversal
  77.           rep (i, s.size()){
  78.                if (!marked[s[i]-'a']){
  79.                     marked[s[i]-'a'] = true;
  80.  
  81. 					//we traverse all checkpoints with same ASCII value and also the corresponding next checkpoints
  82.                     for (auto x : alpha[s[i]]){
  83.                          dist[x] = min(dist[x], dist[i] + abs(s[x] - s[i]));
  84.                     }
  85.                }
  86.           }
  87.  
  88. 		  //for testing each checkpoint cost from starting
  89.           rep (i, s.size()){
  90.                cout << dist[i] << " ";
  91.           }
  92.           cout << "\n";
  93.  
  94.           cout << dist[s.size() - 1] << "\n";
  95.      }
  96.  
  97.      return 0;
  98. }
Success #stdin #stdout 0s 15240KB
comments ()
stdin
copy 
5
asdbksjdfdlfsdfanbkjae
abcdefac
zaxa
zx
ababab
stdout
copy 
0 18 33 35 44 18 27 33 35 33 41 35 18 33 35 0 13 25 44 27 0 4 
4
0 1 2 3 4 5 0 2 
2
0 25 48 25 
25
0 2 
2
0 1 0 1 0 1 
1
https://ideone.com/LcJ9lI
language:
C++14 (gcc 8.3)
created:
7 years 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!