Cod sursa(job #2197487)

Utilizator OpportunityVlad Negura Opportunity Data 22 aprilie 2018 12:37:43
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.39 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:
    const long MAX = 100000000;
    const long MIN = -100000000;
    vector<long> path;
    bool minPath = true;
    bool createPath = true;
    template <class TCost>
    TCost hamilton(DirectedGraph<TCost> graph) {
        // Dynamic programming cost array
        vector<vector<long>> dp(1<<graph.size, vector<long>(graph.size));
        
        // Dynamic programming path array
        vector<vector<long>> dpPath;
        if (createPath) dpPath.resize(1<<graph.size, vector<long>(graph.size));
        
        // for a specific node creat all input edges
        graph.buildInEdges();

        // Init the dp array 
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                dp[i][v] = minPath ? MAX : MIN;
            }
        }
        dp[1][0] = 0;

        // hamilton dp
        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] == MIN || dp[(i ^ (1 << v))][u.from] == MAX) continue;
                    long long newCost = dp[(i ^ (1 << v))][u.from] + (int) u.cost;
                    if (minPath && dp[i][v] > newCost) {
                        dp[i][v] = newCost;
                        if (createPath) 
                            dpPath[(i ^ (1 << v))][v] = u.from;
                    }
                    if (!minPath && dp[i][v] < newCost) {
                        dp[i][v] = newCost;
                        if (createPath) dpPath[(i ^ (1 << v))][v] = u.from;
                    }
                }
            }
        }
  
        // last node dp
        TCost rs = minPath ? MAX : MIN;
        for (auto u:graph.inEdges[0]) {
            if (dp[(1<<graph.size)-1][u.from] == MIN || dp[(1<<graph.size)-1][u.from] == MAX) continue;
            long long newCost = dp[(1<<graph.size)-1][u.from]+u.cost;
            if (minPath && newCost < rs) {
                rs = newCost;
                if (createPath) dpPath[(1<<graph.size)-1][0] = u.from;
            } 
            if (!minPath && newCost > rs) {
                rs = newCost;
                if (createPath) dpPath[(1<<graph.size)-1][0] = u.from;
            }
        }

        if (!createPath) return rs;

        // make path
        long start = 0;
        long long i = (1<<graph.size)-1;
        path.push_back(0);
        do {
            path.push_back(dpPath[i][start]);
            start = dpPath[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;
        }
    }
 
    Hamilton h = Hamilton();
    h.minPath = false;
    h.hamilton(graph);
 
    vector<long> hamiltonPath = h.path;

    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;
}