Advertisement
Guest User

Untitled

a guest
May 29th, 2016
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define endl '\n'
  5. #define mp make_pair
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. string s;
  11. const int NMAX = 1e4;
  12. int parent[NMAX], rnk[NMAX];
  13.  
  14. void make_set (int v) {
  15. parent[v] = v;
  16. rnk[v] = 0;
  17. }
  18.  
  19. int find_set (int v) {
  20. if (v == parent[v])
  21. return v;
  22. return parent[v] = find_set (parent[v]);
  23. }
  24.  
  25. void union_sets (int a, int b) {
  26. a = find_set (a);
  27. b = find_set (b);
  28. if (a != b) {
  29. if (rnk[a] < rnk[b])
  30. swap (a, b);
  31. parent[b] = a;
  32. if (rnk[a] == rnk[b])
  33. ++rnk[a];
  34. }
  35. }
  36.  
  37. bool used[NMAX];
  38.  
  39. int main() {
  40. #if __APPLE__
  41. freopen("input.txt", "r", stdin);
  42. freopen("output.txt", "w", stdout);
  43. #else
  44. freopen("tattarrattat.in", "r", stdin);
  45. freopen("tattarrattat.out", "w", stdout);
  46. #endif
  47. cin >> s;
  48. for (int i = 0; i < s.length(); i++) {
  49. make_set(i);
  50. }
  51. for (int i = 0; i < s.length(); i++) {
  52. for (int j = 0; j < s.length(); j++) {
  53. if (s[i] == s[j] && find_set(i) != find_set(j)) {
  54. union_sets(i, j);
  55. }
  56. }
  57. }
  58. int n = s.length();
  59. for (int i = 0; i < (int)s.length() / 2; i++) {
  60. if (find_set(i) != find_set(n - i - 1)) {
  61. union_sets(i, n - i - 1);
  62. }
  63. }
  64.  
  65. int ans = 0;
  66. for (int i = 0; i < (int)s.length(); ++i){
  67. if (!used[find_set(i)]) {
  68. used[find_set(i)] = true;
  69. int a[27];
  70. for (int j = 0; j < 27; ++j) {
  71. a[j] = 0;
  72. }
  73. pair<int, char> maxx = {0, 'a'};
  74. for (int j = 0; j < (int)s.length(); ++j) {
  75. if (find_set(j) == find_set(i)) {
  76. a[s[j] - 'a']++;
  77. if (a[s[j] - 'a'] > maxx.fi) {
  78. maxx.fi = a[s[j] - 'a'];
  79. maxx.se = s[j];
  80. }
  81. }
  82. }
  83. for (int j = 0; j < (int)s.length(); ++j) {
  84. if (find_set(j) == find_set(i)) {
  85. if (maxx.se != s[j]) {
  86. ans++;
  87. }
  88. }
  89. }
  90. }
  91. }
  92.  
  93. cout << ans;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement