EntropyIncreaser

Untitled

Dec 28th, 2019
420
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define LOG(FMT...) fprintf(stderr, FMT)
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9.  
  10. // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  11.  
  12. template <class T>
  13. istream& operator>>(istream& is, vector<T>& v) {
  14. for (T& x : v)
  15. is >> x;
  16. return is;
  17. }
  18.  
  19. template <class T>
  20. ostream& operator<<(ostream& os, const vector<T>& v) {
  21. if (!v.empty()) {
  22. os << v.front();
  23. for (int i = 1; i < v.size(); ++i)
  24. os << ' ' << v[i];
  25. }
  26. return os;
  27. }
  28.  
  29. const int N = 752, L = 10000010;
  30.  
  31. int n, rt, cnt;
  32. int pos[N];
  33. char s[L];
  34. int ch[L][2];
  35. bitset<N> trans[N];
  36. bool vis[N];
  37. int dfn[N];
  38. int fail[L], prt[L], belongs[L], lst[L];
  39. int f[N];
  40. int sz[N];
  41. bool g[N][N];
  42. int match[N];
  43. bool matched[N];
  44. bool vx[N], vy[N];
  45.  
  46. void dfs(int u) {
  47. static int t;
  48. vis[u] = true;
  49. for (int v = 1; v <= n; ++v)
  50. if (trans[u][v]) {
  51. if (!vis[v])
  52. dfs(v);
  53. trans[u] |= trans[v];
  54. }
  55. dfn[++t] = u;
  56. }
  57.  
  58. bool hgy(int u) {
  59. vis[u] = true;
  60. for (int v = 1; v <= n; ++v)
  61. if (g[u][v]) {
  62. if (!match[v] || (!vis[match[v]] && hgy(match[v]))) {
  63. match[v] = u;
  64. return true;
  65. }
  66. }
  67. return false;
  68. }
  69.  
  70. void dfs2(int u) {
  71. vy[u] = true;
  72.  
  73. }
  74.  
  75. int main() {
  76. #ifdef LBT
  77. freopen("test.in", "r", stdin);
  78. int nol_cl = clock();
  79. #endif
  80.  
  81. ios::sync_with_stdio(false);
  82. cin.tie(nullptr);
  83.  
  84. cin >> n;
  85. rt = cnt = 1;
  86. for (int i = 1; i <= n; ++i) {
  87. cin >> s;
  88. int o = rt;
  89. for (char* p = s; *p; ++p) {
  90. if (!ch[o][*p - 'a']) {
  91. ch[o][*p - 'a'] = ++cnt;
  92. prt[cnt] = o;
  93. }
  94. o = ch[o][*p - 'a'];
  95. }
  96. pos[i] = o;
  97. belongs[o] = i;
  98. }
  99. queue<int> q;
  100. for (int i = 0; i < 2; ++i)
  101. if (ch[rt][i]) {
  102. fail[ch[rt][i]] = rt;
  103. q.push(ch[rt][i]);
  104. }
  105. while (!q.empty()) {
  106. int o = q.front();
  107. q.pop();
  108. for (int i = 0; i < 2; ++i)
  109. if (ch[o][i]) {
  110. int k = fail[o];
  111. while (k != rt && !ch[k][i]) k = fail[k];
  112. k = fail[ch[o][i]] = ch[k][i] ? ch[k][i] : rt;
  113. lst[ch[o][i]] = belongs[k] ? belongs[k] : lst[k];
  114. q.push(ch[o][i]);
  115. }
  116. }
  117. for (int i = 1; i <= n; ++i)
  118. for (int o = pos[i]; o; o = prt[o])
  119. if (lst[o])
  120. trans[i].set(lst[o]);
  121. else if (o != pos[i] && belongs[o])
  122. trans[i].set(belongs[o]);
  123. for (int i = 1; i <= n; ++i)
  124. if (!vis[i])
  125. dfs(i);
  126. cerr << "good\n";
  127. int ans = 0;
  128. for (int i = 1; i <= n; ++i) {
  129. for (int j = 1; j <= n; ++j)
  130. g[i][j] = trans[i][j];
  131. memset(vis, 0, sizeof(vis));
  132. if (hgy(i)) {
  133. ++ans;
  134. }
  135. }
  136. for (int i = 1; i <= n; ++i)
  137. if (match[i]) matched[match[i]] = true;
  138. for (int i = 1; i <= n; ++i) {
  139. if (!match[i])
  140. dfs2(i);
  141. }
  142. cout << n - ans << '\n';
  143. for (int i = 1; i <= n; ++i)
  144. if (!vx[i] && !vy[i]) cout << i << ' ';
  145.  
  146. return 0;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment