Submission #3141806

---

Source Code Expand

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class StronglyConnectedComponents {
public:
    StronglyConnectedComponents(ll n) :
        n_(n),
        edges_(n),
        reverse_edges_(n),
        order_(n),
        num_(0) {}
    
    void addEdge(ll from, ll to) {
        edges_[from].push_back(to);
        reverse_edges_[to].push_back(from);
    }

    vector<vector<ll>> scc() {
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            dfsForward(i);
        }
        sort(order_.begin(), order_.end(), [](const Order& lhs, const Order& rhs) {
            return lhs.order > rhs.order;
        });
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            auto curr_result = dfsBackward(order_[i].index);
            if (curr_result.size() == 0) {
                continue;
            }
            result_.push_back(curr_result);
        }
        return result_;
    }

    vector<vector<ll>> sccEdges() {
        vector<vector<ll>> scc_edges(result_.size());
        vector<ll> indexToScc(n_);
        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll j : result_[i]) {
                indexToScc[j] = i;
            }
        }

        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll from : result_[i]) {
                for (ll to : edges_[from]) {
                    if (indexToScc[to] == i) {
                        continue;
                    }
                    scc_edges[i].push_back(indexToScc[to]);
                }
            }
        }
        return scc_edges;
    }
private:
    void dfsForward(ll curr) {
        if (visit[curr]) {
            return;
        }
        visit[curr] = true;
        for (ll next : edges_[curr]) {
            dfsForward(next);
        }
        order_[curr] = { curr, num_++ };
        return;
    }

    vector<ll> dfsBackward(ll curr) {
        vector<ll> curr_result;
        if (visit[curr]) {
            return curr_result;
        }
        visit[curr] = true;
        curr_result.push_back(curr);
        for (ll next : reverse_edges_[curr]) {
            auto members = dfsBackward(next);
            for (ll m : members) {
                curr_result.push_back(m);
            }
        }
        return curr_result;
    }

    ll n_;
    vector<vector<ll>> edges_;
    vector<vector<ll>> reverse_edges_;
    struct Order {
        ll index, order;
    };
    vector<Order> order_;
    vector<bool> visit;
    vector<vector<ll>> result_;
    ll num_;
};

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<char> c(n);
    for (ll i = 0; i < n; i++) {
        cin >> c[i];
    }

    StronglyConnectedComponents scc(n);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        scc.addEdge(a, b);
    }

    auto scc_result = scc.scc();
    auto scc_edges = scc.sccEdges();

    ll N = scc_result.size();
    vector<string> scc_chars(N);
    for (ll i = 0; i < N; i++) {
        for (ll j : scc_result[i]) {
            scc_chars[i].push_back(c[j]);
        }
        //ソートしておく
        sort(scc_chars[i].begin(), scc_chars[i].end());
    }

    vector<vector<string>> dp(N + 1, vector<string>(k + 1));

    for (ll i = N - 1; i >= 0; i--) {
        for (ll j = 0; j <= min((ll)scc_result[i].size(), k); j++) {
            string str = scc_chars[i].substr(0, j);
            if (dp[i][j].empty() || dp[i][j] > str) {
                dp[i][j] = str;
            }
            for (ll next : scc_edges[i]) {
                for (ll l = 1; l <= k - j; l++) {
                    if (l > 0 && dp[next][l].empty()) {
                        break;
                    }
                    string tmp = str + dp[next][l];
                    if (dp[i][j + l].empty() || dp[i][j + l] > tmp) {
                        dp[i][j + l] = tmp;
                    }
                }
            }
        }
    }

    string ans;
    for (ll i = 0; i < N; i++) {
        if (dp[i][k].empty()) {
            continue;
        }
        if (ans.empty() || ans > dp[i][k]) {
            ans = dp[i][k];
        }
    }

    cout << (ans.empty() ? "-1" : ans) << endl;
}

Submission Info

Judge Result