Advertisement
Guest User

Untitled

a guest
Nov 12th, 2018
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.47 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx")
  3. #pragma GCC optimize ("unroll-loops")
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10.  
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define sz(x) ((int)x.size ())
  15. #define all(x) (x).begin(), (x).end()
  16. #define re return
  17. #define mp make_pair
  18. #define sqrt(x) sqrt (abs(x))
  19. #define y0 y3451
  20. #define y1 y4562
  21. #define j0 j25624
  22. #define j1 j45624
  23. #define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())
  24. #define dbg2(x, y) cout << x << " " << y << endl;
  25. #define dbg3(x, y, z) cout << x << " " << y << " " << z << endl;
  26. #define rep(i, n) for (int i = 0; i < (n); i++)
  27. #define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
  28.  
  29. typedef pair <int, int> ii;
  30. typedef long long ll;
  31. typedef unsigned long long ull;
  32. typedef double D;
  33. typedef long double ld;
  34. typedef unsigned int uint;
  35. typedef vector <string> vs;
  36. typedef vector <int> vi;
  37. typedef vector <ii> vii;
  38. typedef vector <vi> vvi;
  39.  
  40. template <class T> using _tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  41. template <class T> T abs (T x) { re x > 0 ? x : -x; }
  42. template <class T> T sqr (T x) { re x * x; }
  43. template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
  44. template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
  45.  
  46. #define filename ""
  47.  
  48. const D pi = acos(-1.);
  49. const int N = 1e5 + 12000;
  50. const int inf = 1e9 + 7;
  51.  
  52. int n, m;
  53. int cnt = 1;
  54. int to[N][30];
  55. int gt[N][30];
  56. int link[N];
  57. int pr[N];
  58. int pc[N];
  59. string s[N];
  60. int ok[N];
  61. vii g[N];
  62. int ww[N];
  63.  
  64. int dp[5000][5000];
  65. char pred[5000][5000];
  66. int prm[5000][5000];
  67.  
  68. void add(string& s, int z) {
  69. int cur = 0;
  70. for (auto x : s) {
  71. int z = (int) x - 'A';
  72. if (to[cur][z] == -1) {
  73. to[cur][z] = cnt;
  74. gt[cur][z] = cnt;
  75. pr[cnt] = cur;
  76. pc[cnt] = z;
  77. cnt++;
  78. }
  79. cur = to[cur][z];
  80. }
  81. ok[cur] |= (1 << z);
  82. }
  83.  
  84. int go(int v, int c) {
  85. if (gt[v][c] != -1) re gt[v][c];
  86. if (v == 0) re 0;
  87. re gt[v][c] = go(link[v], c);
  88. }
  89.  
  90.  
  91. int main() {
  92. ios::sync_with_stdio(0);
  93. cin.tie(0);
  94. cout.tie(0);
  95. memset(gt, -1, sizeof(gt));
  96. memset(to, -1, sizeof(to));
  97. memset(dp, -1, sizeof(dp));
  98.  
  99. cin >> n;
  100. for (int i = 0; i < n; i++) {
  101. cin >> s[i], add(s[i], i);
  102. }
  103. queue<int> q;
  104. q.push(0);
  105. while(!q.empty()) {
  106. int best = q.front();
  107. q.pop();
  108. ww[best] = ok[best];
  109. if (best != 0 && pr[best] != 0) {
  110. link[best] = go(link[pr[best]], pc[best]);
  111. }
  112. ww[best] |= ww[link[best]];
  113. for (int i = 0; i < 26; i++)
  114. if (to[best][i] != -1)
  115. q.push(to[best][i]);
  116. }
  117. dp[0][ok[0]] = 0;
  118. pred[0][ok[0]] = 0;
  119. queue<pair<int, int>> qq;
  120. qq.push({0, ok[0]});
  121. ii ans = {-1, -1};
  122. while (!qq.empty()) {
  123. auto best = qq.front();
  124. qq.pop();
  125. int cur = best.fi;
  126. int curm = best.se;
  127. if (__builtin_popcount(curm) == n) {
  128. ans = mp(cur, curm);
  129. break;
  130. }
  131. for (int i = 0; i < 26; i++) {
  132. int nxt = go(cur, i);
  133. int newm = curm | ww[nxt];
  134. if (dp[nxt][newm] == -1) {
  135. dp[nxt][newm] = cur;
  136. prm[nxt][newm] = curm;
  137. pred[nxt][newm] = (char) (i + 'A');
  138. qq.push({nxt, newm});
  139. }
  140. }
  141. }
  142. string hh = "";
  143. while (dp[ans.fi][ans.se] != ans.fi) {
  144. hh += pred[ans.fi][ans.se];
  145. ii tmp = ans;
  146. ans.fi = dp[tmp.fi][tmp.se];
  147. ans.se = prm[tmp.fi][tmp.se];
  148. }
  149. reverse(all(hh));
  150. cout << hh ;
  151.  
  152. return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement