Submission #1455794
Source Code Expand
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<cstdio> #include<set> using namespace std; typedef long long ll; const ll INF = 1145141919; ll d[300][300]; ll n, m, k; string alp; string base; string dfs(ll pos, string now, bool *used, bool isFirst){ if(now.size() >= k) return now; set<string> s; if(now.size() + 1 >= k) s.insert(now + alp[pos]); string emp; for(ll i = 0; i < n; ++i){ if(i != pos && !d[pos][i] && !used[i]){ used[pos] = 1; string add = dfs(i, now + alp[pos], used, 0); used[pos] = 0; if(add.size() >= k) s.insert(add); if(isFirst){ add = dfs(i, now, used, 0); if(add.size() >= k) s.insert(add); } } } auto ret = lower_bound(s.begin(), s.end(), base); return (ret == s.end() ? emp : *ret); } int main(){ cin >> n >> m >> k; for(ll i = 0; i < n; ++i){ for(ll j = 0; j < n; ++j){ d[i][j] = INF; } d[i][i] = 0; } for(ll i = 0; i < k; ++i) base = 'a'; for(ll i = 0; i < n; ++i){ char s; cin >> s; alp += s; } for(ll i = 0; i < m; ++i){ ll a, b; cin >> a >> b; --a; --b; d[a][b] = 0; } for(ll i = 0; i < n; ++i) for(ll j = 0; j < n; ++j) for(ll l = 0; l < n; ++l) d[j][l] = min(d[j][l], d[j][i] + d[i][l]); vector<string> v; for(ll i = 0; i < n; ++i){ bool used[n] = {0}; string now; string add = dfs(i, now, used, 1); if(add.size() >= k) v.push_back(add); } sort(v.begin(), v.end()); cout << (v.size() ? v[0] : "-1") << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 有向グラフ |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1542 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 1152 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 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 | TLE | 2103 ms | 1024 KB |
subtask1_random02.txt | TLE | 2103 ms | 1152 KB |
subtask1_random03.txt | TLE | 2103 ms | 1024 KB |
subtask1_random04.txt | TLE | 2103 ms | 1024 KB |
subtask1_random05.txt | AC | 1834 ms | 1024 KB |
subtask1_special01.txt | TLE | 2103 ms | 1152 KB |
subtask1_special02.txt | TLE | 2103 ms | 896 KB |
subtask1_special03.txt | TLE | 2103 ms | 1024 KB |
subtask1_special04.txt | TLE | 2103 ms | 1024 KB |
subtask1_special05.txt | TLE | 2103 ms | 1024 KB |
subtask1_special06.txt | TLE | 2103 ms | 1152 KB |
subtask1_special07.txt | TLE | 2103 ms | 1024 KB |
subtask1_special08.txt | TLE | 2103 ms | 1152 KB |
subtask1_special09.txt | TLE | 2103 ms | 1152 KB |
subtask1_special10.txt | TLE | 2103 ms | 1152 KB |
subtask1_special11.txt | TLE | 2103 ms | 1152 KB |
subtask1_special12.txt | TLE | 2103 ms | 1152 KB |
subtask1_special13.txt | TLE | 2103 ms | 1152 KB |
subtask1_special14.txt | AC | 32 ms | 1024 KB |
subtask1_special15.txt | TLE | 2103 ms | 1024 KB |