Cod sursa(job #2801027)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 14 noiembrie 2021 18:35:07
Problema ADN Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.84 kb
    
#include <bits/stdc++.h>
 
using namespace std;
 
inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
 
using vva = vector <vector <array <int, 2>>>;
using vv = vector <vector <int>>;
using v = vector <string>;
 
 
void printSTR(v vec, vv ccc, vva path, array <int, 2> cur) {
    if(cur[0] == 0)
        return;
 
    printSTR(vec, ccc, path, path[cur[0]][cur[1]]);
    int cost = ccc[path[cur[0]][cur[1]][1]][cur[1]];
    if(path[cur[0]][cur[1]][0] == 0) 
        cost = 0;
 
    cout << vec[cur[1]].substr(cost);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    const int INF = 1e9;
 
    auto KMP = [](string str1, string str2) {
        str1 = ' ' + str1;
        str2 = ' ' + str2;
 
        int len = str1.size() - 1, lenn = str2.size() - 1, q = 0;
        vector <int> pi(len + 1);
        for(int i = 2;i <= len;i++) {
            while(q && str1[q + 1] != str1[i]) 
                q = pi[q];
            if(str1[q + 1] == str1[i])
                q++;
 
            pi[i] = q;
        }
 
        q = 0;
        for(int i = 1;i <= lenn;i++)  {
            while(q && str1[q + 1] != str2[i])
                q = pi[q];
            if(str1[q + 1] == str2[i])
                q++;
            if(q == len)
                return 1;
        }
        return 0;
    };
 
    auto LenPS = [](string str1, string str2) {
        string str = "2" + str2 + "2" +  str1;
 
        int len = str.size(), q = 0;
        vector <int> pi(len);
 
        //pi[1] = 0;
        for(int i = 2;i < len;i++) {
            while(q && str[q + 1] != str[i])
                q = pi[q];
            if(str[q + 1] == str[i])
                q++;
            pi[i] = q; 
        }
 
        return pi.back();
    };
 
    auto cmp = [](string str1, string str2) {
        return str1.size() < str2.size();
    };
 
    Open("adn");
 
    int N; cin >> N;
    vector <string> v(N);
    for(string &x : v)
        cin >> x;
 
    sort(v.begin(), v.end(), cmp);
    vector <bool> marked(N);
    for(int i = 0;i < N - 1;i++)
        for(int j = i + 1;j < N;j++)
            if(KMP(v[i], v[j]) == 1) {
                marked[i] = 1;
                break;
            }
 
    for(int i = 0, cnt = 0;i < N;i++) {
        if(marked[i]) {
            v.erase(v.begin() + i - cnt);
            cnt++;
        }
    }
 
    N = v.size();
    vector <vector <array <int, 2>>> Gr(N);
    vector <vector <int>> cost(N, vector <int>(N));
    for(int i = 0;i < N;i++)
        for(int j = 0;j < N;j++)  
            if(i != j) {
                int val = LenPS(v[i], v[j]);
                Gr[j].push_back({i, val});
                cost[i][j] = val;
            }
 
    int limit = 1 << N;
    vector <vector <int>> dp(limit, vector <int>(N, -INF));
    vector <vector <array <int, 2>>> path(limit, vector <array <int, 2>>(N));
 
    for(int i = 0;i < N;i++)
        dp[1 << i][i] = 0;
 
    for(int i = 0;i < limit;i++)
        for(int j = 0;j < N;j++) {
            if((i & (1 << j)) == 0)
                continue;
 
            for(array <int, 2> it : Gr[j]) {
                if((i & (1 << it[0])) == 0)
                    continue;
 
                if(dp[i ^ (1 << j)][it[0]] + it[1] > dp[i][j]) {
                    dp[i][j] = dp[i ^ (1 << j)][it[0]] + it[1];
                    path[i][j] = {i ^ (1 << j), it[0]};
                }
 
            }
        }
 
    int ans = -INF;
    array <int, 2> ppp;
 
    for(int i = 0;i < N;i++){
        if(dp[limit - 1][i] > ans) {
            ans = dp[limit - 1][i];
            ppp = {limit - 1, i};
        }
    }
 
    printSTR(v, cost, path, ppp);
 
    return 0;
}