Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- //#pragma GCC target("avx")
- #pragma GCC optimize ("unroll-loops")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define fi first
- #define se second
- #define pb push_back
- #define sz(x) ((int)x.size ())
- #define all(x) (x).begin(), (x).end()
- #define re return
- #define mp make_pair
- #define sqrt(x) sqrt (abs(x))
- #define y0 y3451
- #define y1 y4562
- #define j0 j25624
- #define j1 j45624
- #define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())
- #define dbg2(x, y) cout << x << " " << y << endl;
- #define dbg3(x, y, z) cout << x << " " << y << " " << z << endl;
- #define rep(i, n) for (int i = 0; i < (n); i++)
- #define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
- typedef pair <int, int> ii;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef double D;
- typedef long double ld;
- typedef unsigned int uint;
- typedef vector <string> vs;
- typedef vector <int> vi;
- typedef vector <ii> vii;
- typedef vector <vi> vvi;
- template <class T> using _tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- template <class T> T abs (T x) { re x > 0 ? x : -x; }
- template <class T> T sqr (T x) { re x * x; }
- template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
- template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
- #define filename ""
- const D pi = acos(-1.);
- const int N = 1e5 + 12000;
- const int inf = 1e9 + 7;
- int n, m;
- int cnt = 1;
- int to[N][30];
- int gt[N][30];
- int link[N];
- int pr[N];
- int pc[N];
- string s[N];
- int ok[N];
- vii g[N];
- int ww[N];
- int dp[5000][5000];
- char pred[5000][5000];
- int prm[5000][5000];
- void add(string& s, int z) {
- int cur = 0;
- for (auto x : s) {
- int z = (int) x - 'A';
- if (to[cur][z] == -1) {
- to[cur][z] = cnt;
- gt[cur][z] = cnt;
- pr[cnt] = cur;
- pc[cnt] = z;
- cnt++;
- }
- cur = to[cur][z];
- }
- ok[cur] |= (1 << z);
- }
- int go(int v, int c) {
- if (gt[v][c] != -1) re gt[v][c];
- if (v == 0) re 0;
- re gt[v][c] = go(link[v], c);
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- memset(gt, -1, sizeof(gt));
- memset(to, -1, sizeof(to));
- memset(dp, -1, sizeof(dp));
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> s[i], add(s[i], i);
- }
- queue<int> q;
- q.push(0);
- while(!q.empty()) {
- int best = q.front();
- q.pop();
- ww[best] = ok[best];
- if (best != 0 && pr[best] != 0) {
- link[best] = go(link[pr[best]], pc[best]);
- }
- ww[best] |= ww[link[best]];
- for (int i = 0; i < 26; i++)
- if (to[best][i] != -1)
- q.push(to[best][i]);
- }
- dp[0][ok[0]] = 0;
- pred[0][ok[0]] = 0;
- queue<pair<int, int>> qq;
- qq.push({0, ok[0]});
- ii ans = {-1, -1};
- while (!qq.empty()) {
- auto best = qq.front();
- qq.pop();
- int cur = best.fi;
- int curm = best.se;
- if (__builtin_popcount(curm) == n) {
- ans = mp(cur, curm);
- break;
- }
- for (int i = 0; i < 26; i++) {
- int nxt = go(cur, i);
- int newm = curm | ww[nxt];
- if (dp[nxt][newm] == -1) {
- dp[nxt][newm] = cur;
- prm[nxt][newm] = curm;
- pred[nxt][newm] = (char) (i + 'A');
- qq.push({nxt, newm});
- }
- }
- }
- string hh = "";
- while (dp[ans.fi][ans.se] != ans.fi) {
- hh += pred[ans.fi][ans.se];
- ii tmp = ans;
- ans.fi = dp[tmp.fi][tmp.se];
- ans.se = prm[tmp.fi][tmp.se];
- }
- reverse(all(hh));
- cout << hh ;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement