Submission #287878


Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int BUF = 305;
const string NG = string(1, 'z' + 1);

int nNode, nPick;
char ch[BUF];
bool adj[BUF][BUF];

void read() {
    memset(adj, 0, sizeof(adj));
    
    int nEdge;
    cin >> nNode >> nEdge >> nPick;
    
    for (int i = 0; i < nNode; ++i)
        cin >> ch[i];
    
    for (int i = 0; i < nEdge; ++i) {
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        adj[s][t] = true;
    }
}

void dfs(int groupid, vector<int> &order, int id2group[BUF], bool visited[BUF]) {
    visited[groupid] = true;
    for (int i = 0; i < nNode; ++i) {
        if (adj[groupid][id2group[i]] && !visited[id2group[i]])
            dfs(id2group[i], order, id2group, visited);
    }
    order.push_back(groupid);
}

void work() {
    bool origAdj[BUF][BUF];
    for (int i = 0; i < nNode; ++i)
        for (int j = 0; j < nNode; ++j)
            origAdj[i][j] = adj[i][j];
    
    for (int k = 0; k < nNode; ++k)
        for (int i = 0; i < nNode; ++i)
            for (int j = 0; j < nNode; ++j)
                adj[i][j] |= adj[i][k] & adj[k][j];
    
    int id2group[BUF];
    memset(id2group, -1, sizeof(id2group));
    
    for (int i = 0; i < nNode; ++i) {
        if (id2group[i] == -1)
            id2group[i] = i;
        else
            continue;
        
        for (int j = i + 1; j < nNode; ++j) {
            if (id2group[j] != -1)
                continue;
            if (adj[i][j] && adj[j][i]) {
                id2group[j] = i;
            }
        }
    }

    vector<int> order;
    bool visited[BUF] = {};
    for (int i = 0; i < nNode; ++i) {
        if (visited[id2group[i]])
            continue;
        dfs(id2group[i], order, id2group, visited);
    }
    
    bool groupAdj[BUF][BUF] = {};
    for (int i = 0; i < nNode; ++i)
        for (int j = 0; j < nNode; ++j)
            groupAdj[id2group[i]][id2group[j]] |= origAdj[i][j];
    
    string group2str[BUF];
    for (int i = 0; i < nNode; ++i)
        group2str[id2group[i]] += ch[i];
    
    for (int i = 0; i < nNode; ++i)
        sort(group2str[i].begin(), group2str[i].end());
    
    string dp[BUF][BUF];
    for (int i = 0; i < nNode; ++i)
        for (int j = 0; j <= nPick; ++j)
            dp[i][j] = NG;
    
    for (int i = 0; i < order.size(); ++i) {
        int groupId = order[i];
        
        for (int nCh = 0; nCh <= group2str[groupId].size(); ++nCh)
            dp[groupId][nCh] = group2str[groupId].substr(0, nCh);
        
        for (int j = 0; j < i; ++j) {
            int oppGroupId = order[j];
            
            if (!groupAdj[groupId][oppGroupId])
                continue;
            
            for (int nCh = 0; nCh <= nPick; ++nCh) {
                for (int nSelfCh = 0; nSelfCh <= nCh; ++nSelfCh) {
                    if (group2str[groupId].size() < nSelfCh)
                        continue;
                    
                    if (dp[oppGroupId][nCh - nSelfCh] == NG)
                        continue;
                
                    dp[groupId][nCh] = min(dp[groupId][nCh],
                                           group2str[groupId].substr(0, nSelfCh) + dp[oppGroupId][nCh - nSelfCh]);
                }
            }
        }
    }
    
    string ans = NG;
    for (int i = 0; i < nNode; ++i)
        ans = min(ans, dp[i][nPick]);
    cout << (ans == NG ? "-1" : ans) << endl;
}


int main() {
    read();
    work();
    return 0;
}

Submission Info

Submission Time
Task C - 有向グラフ
User Hachimori
Language C++ (G++ 4.6.4)
Score 100
Code Size 3633 Byte
Status AC
Exec Time 123 ms
Memory 7980 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 32
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 23 ms 1624 KB
subtask0_sample_02.txt AC 22 ms 1828 KB
subtask0_sample_03.txt AC 23 ms 1816 KB
subtask0_sample_04.txt AC 23 ms 1828 KB
subtask1_manual01.txt AC 24 ms 1696 KB
subtask1_manual02.txt AC 24 ms 1824 KB
subtask1_manual03.txt AC 23 ms 1708 KB
subtask1_manual04.txt AC 24 ms 1704 KB
subtask1_manual05.txt AC 23 ms 1828 KB
subtask1_manual06.txt AC 23 ms 1692 KB
subtask1_manual07.txt AC 23 ms 1824 KB
subtask1_manual08.txt AC 24 ms 1708 KB
subtask1_random01.txt AC 80 ms 1956 KB
subtask1_random02.txt AC 77 ms 1772 KB
subtask1_random03.txt AC 84 ms 2084 KB
subtask1_random04.txt AC 80 ms 1952 KB
subtask1_random05.txt AC 79 ms 1768 KB
subtask1_special01.txt AC 77 ms 1760 KB
subtask1_special02.txt AC 78 ms 1952 KB
subtask1_special03.txt AC 91 ms 3880 KB
subtask1_special04.txt AC 110 ms 6696 KB
subtask1_special05.txt AC 122 ms 7972 KB
subtask1_special06.txt AC 101 ms 3880 KB
subtask1_special07.txt AC 91 ms 2912 KB
subtask1_special08.txt AC 101 ms 3880 KB
subtask1_special09.txt AC 100 ms 3800 KB
subtask1_special10.txt AC 102 ms 3884 KB
subtask1_special11.txt AC 97 ms 3368 KB
subtask1_special12.txt AC 95 ms 3040 KB
subtask1_special13.txt AC 95 ms 2856 KB
subtask1_special14.txt AC 76 ms 1828 KB
subtask1_special15.txt AC 123 ms 7980 KB