Submission #3170155

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

struct DirectedGraph
{
    int V; // 頂点数
    vector<vector<int> > to;
    vector<vector<int> > from;

    vector<bool> used;
    vector<int> vs;

    void dfs(int v)
    {
        used[v] = true;
        for (auto t : to[v]) if (!used[t]) dfs(t);
        vs.push_back(v);
    }
    void rdfs(int v, int k)
    {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v]) if (!used[t]) rdfs(t, k);
    }

    vector<int> cmp;
    DirectedGraph(int V) : V(V),
                           to(vector<vector<int> >(V)), 
                           from(vector<vector<int> >(V)),
                           cmp(vector<int>(V))
                           {}
    void add_edge(int from_, int to_)
    {
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    int scc_num = -1;
    int scc()
    {
        used = vector<bool>(V, false);
        vs.clear();
        for (int v = 0; v < V; v++) if (!used[v]) dfs(v);

        used = vector<bool>(V, false);
        scc_num = 0;
        for (int i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) rdfs(vs[i], scc_num++);
        return scc_num;
    }

    // scc()を実行したあと，強連結成分を潰したトポロジカル順序のグラフを生成
    DirectedGraph generateTopologicalGraph()
    {
        DirectedGraph newgraph(scc_num);
        REP(s, V) for (auto t : to[s])
        {
            if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]);
        }
        return newgraph;
    }
};

int n, m, k;
vector<char> c;

int main()
{
    cin >> n >> m >> k;
    c.resize(n);
    REP(i, n) cin >> c[i];

    DirectedGraph graph(n);
    REP(i, m)
    {
        int a, b;
        cin >> a >> b;
        graph.add_edge(a - 1, b - 1);
    }
    int ngroup = graph.scc();
    vector<int> sz_group(ngroup);
    for (auto v : graph.cmp) sz_group[v]++;
    vector<int> sz_children(ngroup);

    DirectedGraph topgraph = graph.generateTopologicalGraph();
    IREP(i, topgraph.V) for (auto v : topgraph.from[i])
    {
        sz_children[v] = max(sz_children[v], sz_children[i] + sz_group[i]);
    }

    vector<vector<int> > count(ngroup, vector<int>(26));
    REP(i, n) count[graph.cmp[i]][c[i] - 'a']++;

    vector<string> st(ngroup);
    REP(i, ngroup)
    {
        string tmp;
        REP(c, 26) REP(_, count[i][c]) tmp += (char)(c + 'a');
        st[i] = tmp;
        for (auto prev : topgraph.from[i])
        {
            string tmp2 = st[prev];
            while (tmp2.length() && tmp2.length() + tmp.length() + sz_children[i] > k && tmp2.back() > tmp[0]) tmp2.pop_back();
            if (st[i].length() + sz_children[i] < k) st[i] = tmp2 + tmp;
            else 
            {
                st[i] = min(st[i] + (char)('z' + 1), tmp2 + tmp + (char)('z' + 1));
                st[i].pop_back();
            }
        }
    }

    string ans;
    ans += (char)('z' + 1);

    for (auto str : st)
    {
        if (str.length() >= k)
        {
            ans = min(ans, str.substr(0, k));
        }
    }
    if (ans.length() == k) cout << ans << endl;
    else cout << -1 << endl;
}

Submission Info

Judge Result