Cod sursa(job #2193772)

Utilizator OpportunityVlad Negura Opportunity Data 11 aprilie 2018 15:07:09
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.2 kb
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()

ifstream fi("adn.in");
ofstream fo("adn.out");

template <class TCost>
class Graph {
public:
    struct Edge {
        long from, to;
        TCost cost;
        Edge(long _from, long _to, TCost _cost): from(_from), to(_to), cost(_cost) {};
    };
    long size;
    bool zeroIndexed;
    vector<Edge> edges;
    vector<vector<pair<long, TCost>>> adjacencyList;
    Graph() {};
    Graph(long _size, bool _zeroIndexed = true) {
        zeroIndexed = _zeroIndexed;
        if (!zeroIndexed) _size++;
        size = _size;
        adjacencyList.resize(_size);
    };
    ~Graph() = default;
};
template <class TCost>
class DirectedGraph : public Graph<TCost> {
public:
    using typename Graph<TCost>::Edge;
    vector<vector<Edge>> inEdges;
    DirectedGraph() {};
    DirectedGraph(long _size, bool _zeroIndexed): Graph<TCost>(_size, _zeroIndexed) {};
    DirectedGraph(long _size): Graph<TCost>(_size) {};
    void addEdge(long from, long to, TCost cost = 0) {
        this->edges.push_back({from, to, cost});
        this->adjacencyList[from].push_back({to, cost});
    }
    void printEdges() {
        for (auto edge: this->edges) {
            cout << edge.from << ' ' << edge.to << endl;
        }
    }
    void buildInEdges() {
        inEdges.resize(this->size);
        for (Edge u: this->edges) {
            inEdges[u.to].push_back(u);
        }
    }
};
class Hamilton {
public:
    static vector<long> defaultPath;
    template <class TCost>
    static TCost pathCost(DirectedGraph<TCost> graph, bool minPath = true, vector<long> &path = defaultPath) {
        vector<vector<long long>> dp(1<<graph.size, vector<long long>(graph.size));
        vector<vector<long>> pathParent(1<<graph.size, vector<long>(graph.size));
        graph.buildInEdges();
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                dp[i][v] = minPath?INT32_MAX:INT32_MIN;
            }
        }
        dp[1][0] = 0;
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                if (!(i&(1<<v))) continue;
                for (auto u: graph.inEdges[v]) {
                    if (!(i&(1<<u.from))) continue;
                    if (dp[(i ^ (1 << v))][u.from] == INT32_MIN) continue;
                    if (dp[(i ^ (1 << v))][u.from] == INT32_MAX) continue;
                    long long newCost = dp[(i ^ (1 << v))][u.from] + (int) u.cost;
                    if (minPath) {
                        if (dp[i][v] > newCost) {
                            dp[i][v] = newCost;
                            pathParent[(i ^ (1 << v))][v] = u.from;
                        }
                    } else {
                        if (dp[i][v] < newCost) {
                            dp[i][v] = newCost;
                            pathParent[(i ^ (1 << v))][v] = u.from;
                        }
                    }
                }
            }
        }


        TCost rs = minPath?INT32_MAX:INT32_MIN;
        for (auto u:graph.inEdges[0]) {
            if (dp[(1<<graph.size)-1][u.from] == INT32_MIN) continue;
            if (dp[(1<<graph.size)-1][u.from] == INT32_MAX) continue;
            long long newCost = dp[(1<<graph.size)-1][u.from]+u.cost;
            if (minPath) {
                if (newCost < rs) {
                    rs = newCost;
                    pathParent[(1<<graph.size)-1][0] = u.from;
                }
            } else {
                if (newCost > rs) {
                    rs = newCost;
                    pathParent[(1<<graph.size)-1][0] = u.from;
                }
            }
        }

        // make path
        long start = 0;
        long long i = (1<<graph.size)-1;
        path.push_back(0);
        do {
            path.push_back(pathParent[i][start]);
            start = pathParent[i][start];
            i = i^(1<<start);
        } while (start != 0);

        reverse(path.begin(),path.end());

        return rs;
    }
};

struct Comp {
    bool operator() (const string & s1, const string & s2) {
        return s1.size() > s2.size();
    }
};

vector<string> exclude(vector<string> a) {
    vector<string> b = {};
    sort(all(a), Comp());
    b.push_back(a[0]);

    rep(i,1,a.size()) {
        bool good = true;
        rep(j,0,i) {
            if (a[j].find(a[i]) != string::npos) {
                good = false;
                break;
            }
        }
        if (good) b.push_back(a[i]);
    }

    return b;
}

ll findCost(string s1, string s2) {
    int rs=0;
    for (int i=min(s1.size(), s2.size()); i>=0; i--) {
        string a2 = s2.substr(0,i);
        string a1 = s1.substr(s1.size()-i, i);
        if (a2 == a1) return i;
    }
    return 0;
}

ll n;
vector<string> a;
string RS;

void updateRs(deque<long> &q, vector<vector<ll>> &costMatrix) {
    string rs = a[q[0]];
    for (int i=1; i<q.size(); i++) {
        ll cost = costMatrix[q[i-1]][q[i]];
        string s = a[q[i]];
        rs += s.substr(cost, s.size()-cost);
    }
    if (rs.size() < RS.size() || RS == "") {
        RS = rs;
    }
}


int main() {_
    fi >> n;
    a.resize(n);

    for (int i=0; i<n; i++) fi >> a[i];

    a = exclude(a);
    n = a.size();

    vector<vector<ll>> costMatrix(n, vector<ll>(n));
    DirectedGraph<ll> graph = DirectedGraph<ll>(n);
    rep(i,0,n) {
        rep(j,i+1,n) {
            ll cost = findCost(a[i], a[j]);
            graph.addEdge(i,j, cost);
            costMatrix[i][j] = cost;
            cost = findCost(a[j],a[i]);
            graph.addEdge(j,i,cost);
            costMatrix[j][i] = cost;
        }
    }

    vector<long> hamiltonPath;
    Hamilton::pathCost(graph, false, hamiltonPath);

    deque<long> q;
    for (int i=1; i<hamiltonPath.size(); i++) {
        q.push_back(hamiltonPath[i]);
    }

    for (int i=0;i<hamiltonPath.size(); i++) {
        updateRs(q, costMatrix);
        q.push_front(q.back());
        q.pop_back();
    }

    fo << RS;

    return 0;
}