Submission #1455818


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 dfs(ll pos, string now, bool *used, bool isFirst){
	if(now.size() >= k) return now;
	string ret;
	if(now.size() + 1 >= k) ret = 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 && (ret.empty() || ret > add)) ret = add;
			if(isFirst){
				add = dfs(i, now, used, 0);
				if(add.size() >= k && (ret.empty() || ret > add)) ret = add;
			}
		}
	}
	return (ret.empty() ? 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 < 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]);
	
	string ans;
	for(ll i = 0; i < n; ++i){
		bool used[n] = {0};
		string now;
		string add = dfs(i, now, used, 1);
		if(add.size() >= k && (ans.empty() || ans > add)) ans = add;
	}
	cout << (ans.size() ? ans : "-1") << endl;
	return 0;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 4
AC × 14
TLE × 18
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 896 KB
subtask1_random03.txt TLE 2103 ms 1024 KB
subtask1_random04.txt TLE 2103 ms 1024 KB
subtask1_random05.txt AC 1492 ms 896 KB
subtask1_special01.txt TLE 2103 ms 1024 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 1024 KB
subtask1_special07.txt TLE 2103 ms 1024 KB
subtask1_special08.txt TLE 2103 ms 1024 KB
subtask1_special09.txt TLE 2103 ms 1024 KB
subtask1_special10.txt TLE 2103 ms 1024 KB
subtask1_special11.txt TLE 2103 ms 1024 KB
subtask1_special12.txt TLE 2103 ms 1024 KB
subtask1_special13.txt TLE 2103 ms 1024 KB
subtask1_special14.txt AC 32 ms 896 KB
subtask1_special15.txt TLE 2103 ms 1024 KB