Submission #1501137


Source Code Expand

// {{{ Templates
#include <bits/stdc++.h>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

// }}}

struct DGraph {
    using T = int;
    DGraph(const int v) : V{v}
    {
        edge.resize(v);
        rev_edge.resize(v);
    }
    struct Edge {
        Edge(const int from, const int to, const T cost) : from{from}, to{to}, cost{cost} {}
        const int from;
        const int to;
        const T cost;
        bool operator<(const Edge& e) const
        {
            return cost != e.cost ? cost < e.cost : to < e.to;
        }
    };
    void addEdge(const int from, const int to, const T cost)
    {
        edge[from].push_back(Edge{from, to, cost});
        rev_edge[to].push_back(Edge(to, from, cost));
    }
    vector<vector<Edge>> edge;
    vector<vector<Edge>> rev_edge;
    const int V;
};
void dfs1_scc(const DGraph& g, const int s, vector<int>& st, vector<bool>& used)
{
    assert(s < g.V);
    assert(used.size() == g.V);
    used[s] = true;
    for (const auto& e : g.edge[s]) {
        if (not used[e.to]) {
            dfs1_scc(g, e.to, st, used);
        }
    }
    st.push_back(s);
}
void dfs2_scc(const DGraph& g, const int s, const int index, vector<int>& cmp, vector<bool>& used)
{
    assert(s < g.V);
    assert(index < g.V);
    assert(cmp.size() == g.V);
    cmp[s] = index;
    used[s] = true;
    for (const auto& e : g.rev_edge[s]) {
        if (not used[e.to]) {
            dfs2_scc(g, e.to, index, cmp, used);
        }
    }
};
int SCC(const DGraph& g, vector<int>& cmp)
{
    assert(cmp.size() == g.V);
    for (int i = 0; i < g.V; i++) {
        cmp[i] = 0;
    }

    vector<int> st;
    vector<bool> used(g.V, false);
    for (int i = 0; i < g.V; i++) {
        if (not used[i]) {
            dfs1_scc(g, i, st, used);
        }
    }

    for (int i = 0; i < g.V; i++) {
        used[i] = false;
    }
    int comp = 0;
    for (int i = 0; i < st.size(); i++) {
        const int s = st[st.size() - i - 1];
        if (not used[s]) {
            dfs2_scc(g, s, comp++, cmp, used);
        }
    }
    return comp;
}
void dfs_topo(const DGraph& g, const int s, vector<bool>& used, vector<int>& srt)
{
    assert(s < g.V);
    assert(used.size() == g.V);
    if (not used[s]) {
        used[s] = true;
        for (const auto& e : g.edge[s]) {
            dfs_topo(g, e.to, used, srt);
        }
        srt.push_back(s);
    }
}
void TopologocalSort(const DGraph& g, vector<int>& srt)
{
    srt.clear();
    vector<bool> used(g.V, false);
    for (int i = 0; i < g.V; i++) {
        dfs_topo(g, i, used, srt);
    }
    reverse(srt.begin(), srt.end());
}

int n, m, k;
void dp_dfs(const DGraph& g, const int s, const int prev, const vector<int>& comp, const vector<string>& compst, vector<vector<string>>& dp, vector<bool>& compused, vector<bool>& visited, const vector<string>& dummy)
{
    if (visited[s]) {
        return;
    }
    visited[s] = true;
    if (not compused[comp[s]]) {
        if (prev == -1) {
            for (int i = 0; i <= min(k, (int)compst[comp[s]].size()); i++) {
                dp[comp[s]][i] = min(dp[comp[s]][i], compst[comp[s]].substr(0, i));
            }
        } else {
            for (int i = 0; i <= k; i++) {
                for (int j = 0; j <= min(i, (int)compst[comp[s]].size()); j++) {
                    const string str = dp[comp[prev]][i - j] + compst[comp[s]].substr(0, j);
                    dp[comp[s]][i] = min(dp[comp[s]][i], str);
                }
            }
        }
        compused[comp[s]] = true;
    }
    for (const auto& e : g.edge[s]) {
        const int to = e.to;
        dp_dfs(g, to, s, comp, compst, dp, compused, visited, dummy);
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g.addEdge(a, b, 1);
    }
    vector<int> comp(n);
    const int compnum = SCC(g, comp);

    vector<int> srt(n);
    TopologocalSort(g, srt);

    vector<string> compst(compnum);
    for (int i = 0; i < n; i++) {
        compst[comp[i]].push_back(c[i]);
    }
    for (int i = 0; i < compnum; i++) {
        sort(compst[i].begin(), compst[i].end());
    }

    vector<string> dummy(k + 1);
    for (int i = 1; i <= k; i++) {
        dummy[i] = dummy[i - 1];
        dummy[i].push_back('z' + 1);
    }

    vector<vector<string>> dp(compnum, vector<string>(k + 1));  // comp, kind
    for (int i = 0; i < compnum; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dummy[j];
        }
    }
    vector<bool> compused(compnum, false);
    vector<bool> visited(n, false);

    for (const int s : srt) {
        if (not visited[s]) {
            dp_dfs(g, s, -1, comp, compst, dp, compused, visited, dummy);
        }
    }

    string st = dummy[k];
    for (int i = 0; i < compnum; i++) {
        st = min(st, dp[i][k]);
    }
    for (const char ch : st) {
        if (ch == 'z' + 1) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << st << endl;

    return 0;
}

Submission Info

Submission Time
Task C - 有向グラフ
User pachicobue
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5980 Byte
Status WA
Exec Time 48 ms
Memory 17920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 4
AC × 28
WA × 4
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_manual01.txt, subtask1_manual02.txt, subtask1_manual03.txt, subtask1_manual04.txt, subtask1_manual05.txt, subtask1_manual06.txt, subtask1_manual07.txt, subtask1_manual08.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt, subtask1_special11.txt, subtask1_special12.txt, subtask1_special13.txt, subtask1_special14.txt, subtask1_special15.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask0_sample_04.txt AC 1 ms 256 KB
subtask1_manual01.txt AC 1 ms 256 KB
subtask1_manual02.txt AC 1 ms 256 KB
subtask1_manual03.txt AC 1 ms 256 KB
subtask1_manual04.txt AC 1 ms 256 KB
subtask1_manual05.txt AC 1 ms 256 KB
subtask1_manual06.txt AC 1 ms 256 KB
subtask1_manual07.txt AC 1 ms 256 KB
subtask1_manual08.txt AC 1 ms 256 KB
subtask1_random01.txt WA 4 ms 640 KB
subtask1_random02.txt WA 2 ms 384 KB
subtask1_random03.txt WA 10 ms 1408 KB
subtask1_random04.txt WA 4 ms 640 KB
subtask1_random05.txt AC 2 ms 384 KB
subtask1_special01.txt AC 1 ms 512 KB
subtask1_special02.txt AC 2 ms 512 KB
subtask1_special03.txt AC 11 ms 3328 KB
subtask1_special04.txt AC 22 ms 9088 KB
subtask1_special05.txt AC 35 ms 17792 KB
subtask1_special06.txt AC 24 ms 6144 KB
subtask1_special07.txt AC 12 ms 2176 KB
subtask1_special08.txt AC 24 ms 6144 KB
subtask1_special09.txt AC 24 ms 6144 KB
subtask1_special10.txt AC 35 ms 6144 KB
subtask1_special11.txt AC 22 ms 4608 KB
subtask1_special12.txt AC 21 ms 3712 KB
subtask1_special13.txt AC 21 ms 3200 KB
subtask1_special14.txt AC 1 ms 384 KB
subtask1_special15.txt AC 48 ms 17920 KB