Submission #287830
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], bool groupAdj[BUF][BUF]) { visited[groupid] = true; for (int i = 0; i < nNode; ++i) { if (groupAdj[groupid][id2group[i]] && !visited[id2group[i]]) dfs(id2group[i], order, id2group, visited, groupAdj); } 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; } } } 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]; vector<int> order; bool visited[BUF] = {}; for (int i = 0; i < nNode; ++i) { if (visited[id2group[i]]) continue; dfs(id2group[i], order, id2group, visited, groupAdj); } 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 | 3687 Byte |
Status | AC |
Exec Time | 127 ms |
Memory | 7964 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 24 ms | 1820 KB |
subtask0_sample_02.txt | AC | 26 ms | 1824 KB |
subtask0_sample_03.txt | AC | 27 ms | 1596 KB |
subtask0_sample_04.txt | AC | 24 ms | 1700 KB |
subtask1_manual01.txt | AC | 24 ms | 1812 KB |
subtask1_manual02.txt | AC | 23 ms | 1824 KB |
subtask1_manual03.txt | AC | 24 ms | 1696 KB |
subtask1_manual04.txt | AC | 24 ms | 1640 KB |
subtask1_manual05.txt | AC | 24 ms | 1692 KB |
subtask1_manual06.txt | AC | 22 ms | 1820 KB |
subtask1_manual07.txt | AC | 24 ms | 1828 KB |
subtask1_manual08.txt | AC | 23 ms | 1828 KB |
subtask1_random01.txt | AC | 81 ms | 1964 KB |
subtask1_random02.txt | AC | 78 ms | 1888 KB |
subtask1_random03.txt | AC | 87 ms | 2092 KB |
subtask1_random04.txt | AC | 79 ms | 1952 KB |
subtask1_random05.txt | AC | 75 ms | 1828 KB |
subtask1_special01.txt | AC | 76 ms | 1832 KB |
subtask1_special02.txt | AC | 77 ms | 1956 KB |
subtask1_special03.txt | AC | 91 ms | 3868 KB |
subtask1_special04.txt | AC | 107 ms | 6696 KB |
subtask1_special05.txt | AC | 121 ms | 7964 KB |
subtask1_special06.txt | AC | 100 ms | 3880 KB |
subtask1_special07.txt | AC | 93 ms | 2916 KB |
subtask1_special08.txt | AC | 103 ms | 3868 KB |
subtask1_special09.txt | AC | 99 ms | 3876 KB |
subtask1_special10.txt | AC | 100 ms | 3848 KB |
subtask1_special11.txt | AC | 98 ms | 3372 KB |
subtask1_special12.txt | AC | 103 ms | 2928 KB |
subtask1_special13.txt | AC | 99 ms | 2852 KB |
subtask1_special14.txt | AC | 76 ms | 1820 KB |
subtask1_special15.txt | AC | 127 ms | 7964 KB |