Submission #4036083


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;

ll N, M, K;
vector<vector<ll>> edges(300);
vector<vector<ll>> ge;
vector<string> gstr;
const string INF = string(310, 'z');

class StrongDisassembly{

    private:
        ll V;
        vector<vector<ll>> E;
        vector<vector<ll>> inv_E;
        ll *number;
        bool *used_dfs;
        ll to_write_num = 0;

        void dfs(ll now){
            used_dfs[now] = 1;
            for(ll next : E[now]){
                if(used_dfs[next]){
                    continue;
                }
                dfs(next);
            }
            number[now] = to_write_num++;
        }

        void dfs(ll now, bool *used, vector<ll> &ret){
            used[now] = 1;
            ret.push_back(now);
            for(ll next : inv_E[now]){
                if(used[next]){
                    continue;
                }
                dfs(next, used, ret);
            }
        }

        void write_num(){
            for(ll i = 0; i < V; i++){
                if(!used_dfs[i]){
                    dfs(i);
                }
            }
        }

    public:
        StrongDisassembly(const vector<vector<ll>> &e){
            V = e.size();
            E = e;
            inv_E = vector<vector<ll>>(V);
            number = new ll[V];
            used_dfs = new bool[V];
            for(ll i = 0; i < V; i++){
                used_dfs[i] = 0;
                inv_E.push_back(vector<ll>(0));
            }
            for(ll i = 0; i < V; i++){
                for(ll next : e[i]){
                    inv_E[next].push_back(i);
                }
            }
            write_num();
        }

        vector<vector<ll>> disassembly(){
            vector<vector<ll>> ret;
            vector<ll> vec;
            bool used[V] = {};
            for(ll i = 0; i < V; i++){
                vec.push_back(i);
            }
            sort(vec.begin(), vec.end(), [&](ll a, ll b){
                    return number[a] > number[b];
                    }
                );
            for(ll vertex : vec){
                if(used[vertex]){
                    continue;
                }
                vector<ll> to_insert;
                dfs(vertex, used, to_insert);
                ret.push_back(to_insert);
            }
            return ret;
        }
};

vector<string> dfs(ll now){
    vector<string> memo(K + 1, INF);
    memo[0] = "";
    for(ll nxt : ge[now]){
        const auto tmp = move(dfs(nxt));
        for(ll j = 0; j <= K; j++) memo[j] = min(memo[j], tmp[j]);
    }
    auto update = memo;
    for(ll i = 1; i <= gstr[now].size(); i++){
        for(ll j = 0; i + j <= K; j++){
            if(memo[j] != INF){
                update[i + j] = min(memo[i + j], gstr[now].substr(0, i) + memo[j]);
            }
        }
    }
    return update;
}

int main(){
    cin >> N >> M >> K;
    vector<char> S(N);
    set<P> se;
    for(char &c : S) cin >> c;
    for(ll i = 0; i < M; i++){
        ll a, b;
        cin >> a >> b;
        edges[--a].push_back(--b);
        se.insert(P(a, b));
    }
    edges.resize(N);
    auto g = StrongDisassembly(edges).disassembly();
    ge = decltype(ge)(g.size());
    gstr = decltype(gstr)(g.size());
    vector<ll> rev(N);
    for(ll i = 0; i < g.size(); i++) for(ll e : g[i]) rev[e] = i;
    vector<bool> has_parent(ge.size(), false);
    for(ll i = 0; i < N; i++) for(ll j = 0; j < N; j++) if(se.find(P(i, j)) != se.end() && rev[i] != rev[j]){
        ge[rev[i]].push_back(rev[j]);
        has_parent[rev[j]] = true;
    }
    for(auto &v : ge){
        sort(v.begin(), v.end());
        auto ite = unique(v.begin(), v.end());
        v.erase(ite, v.end());
    }
    for(ll i = 0; i < N; i++) gstr[rev[i]] += S[i];
    for(auto &s : gstr) sort(s.begin(), s.end());
    string ans = INF;
    for(ll i = 0; i < ge.size(); i++){
        if(has_parent[i]) continue;
        const auto tmp = move(dfs(i));
        ans = min(ans, tmp[K]);
    }
    if(ans == INF) ans = "-1";
    cout << ans << endl;
    return 0;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 4
AC × 21
WA × 11
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 8 ms 384 KB
subtask1_random02.txt WA 5 ms 384 KB
subtask1_random03.txt WA 11 ms 384 KB
subtask1_random04.txt WA 6 ms 384 KB
subtask1_random05.txt AC 4 ms 384 KB
subtask1_special01.txt AC 4 ms 384 KB
subtask1_special02.txt AC 3 ms 384 KB
subtask1_special03.txt AC 7 ms 640 KB
subtask1_special04.txt AC 11 ms 896 KB
subtask1_special05.txt AC 13 ms 1152 KB
subtask1_special06.txt AC 12 ms 512 KB
subtask1_special07.txt WA 9 ms 512 KB
subtask1_special08.txt WA 12 ms 512 KB
subtask1_special09.txt WA 12 ms 512 KB
subtask1_special10.txt WA 12 ms 512 KB
subtask1_special11.txt WA 11 ms 512 KB
subtask1_special12.txt WA 11 ms 512 KB
subtask1_special13.txt WA 11 ms 384 KB
subtask1_special14.txt AC 2 ms 256 KB
subtask1_special15.txt AC 14 ms 1152 KB