Submission #287090


Source Code Expand

Copy
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define maxv 364
vector<int> gr[maxv],rgr[maxv];
vector<int> vs;
bool sumi[maxv];
int cmp[maxv];
char c[maxv];string s[maxv];
int num[maxv][36];
bool ed[maxv][maxv];
string dp[maxv][maxv];
void dfs(int v){
	sumi[v]=true;
	rep(i,gr[v].size()){
		if(!sumi[gr[v][i]]) dfs(gr[v][i]);
	}
	vs.pb(v);
}
void rdfs(int v,int k){
	sumi[v]=true;cmp[v]=k;
	rep(i,rgr[v].size()){
		if(!sumi[rgr[v][i]]) rdfs(rgr[v][i],k);
	}
}
int scc(int n)
{
	memset(sumi,false,sizeof(sumi));
	vs.clear();
	rep(i,n){
		if(!sumi[i]) dfs(i);
	}
	memset(sumi,false,sizeof(sumi));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!sumi[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}
int main(){
	int n,m,x,a,b;
	cin>>n>>m>>x;
	rep(i,n) cin>>c[i];
	rep(i,m){
		cin>>a>>b;a--;b--;
		gr[a].pb(b);rgr[b].pb(a);
	}
	m=scc(n);
	memset(num,0,sizeof(num));
	rep(i,n) s[cmp[i]]+=c[i],num[cmp[i]][(c[i]-'a')]++;
	rep(i,m) sort(All(s[i]));
	memset(ed,false,sizeof(ed));
	rep(i,n) rep(j,gr[i].size()) ed[cmp[i]][cmp[gr[i][j]]]=true;
	string inf="";rep(i,364) inf+='z';rep(i,maxv) rep(j,maxv) dp[i][j]=inf;
	
	for(int i=m-1;i>=0;i--){
		rep(j,s[i].size()+1) dp[i][j]=s[i].substr(0,j);
		rep(j,m){
			if(i==j || !ed[i][j]) continue;
			rep(k,s[i].size()+1) for(int l=0;dp[j][l]<inf;l++) dp[i][k+l]=min(dp[i][k+l],s[i].substr(0,k)+dp[j][l]);
		}
	}
	string out=inf;
	rep(i,m) out=min(out,dp[i][x]);
	if(out>=inf) cout<<-1<<endl;else cout<<out<<endl;
}

Submission Info

Submission Time
Task C - 有向グラフ
User sky58
Language C++ (G++ 4.6.4)
Score 100
Code Size 2156 Byte
Status AC
Exec Time 60 ms
Memory 8232 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 27 ms 2080 KB
subtask0_sample_02.txt AC 27 ms 1960 KB
subtask0_sample_03.txt AC 26 ms 2032 KB
subtask0_sample_04.txt AC 25 ms 1944 KB
subtask1_manual01.txt AC 25 ms 2076 KB
subtask1_manual02.txt AC 26 ms 1952 KB
subtask1_manual03.txt AC 26 ms 1960 KB
subtask1_manual04.txt AC 27 ms 2076 KB
subtask1_manual05.txt AC 26 ms 1952 KB
subtask1_manual06.txt AC 26 ms 1960 KB
subtask1_manual07.txt AC 25 ms 1964 KB
subtask1_manual08.txt AC 25 ms 1952 KB
subtask1_random01.txt AC 32 ms 2592 KB
subtask1_random02.txt AC 34 ms 2732 KB
subtask1_random03.txt AC 32 ms 2464 KB
subtask1_random04.txt AC 30 ms 2344 KB
subtask1_random05.txt AC 32 ms 2732 KB
subtask1_special01.txt AC 27 ms 2080 KB
subtask1_special02.txt AC 59 ms 8220 KB
subtask1_special03.txt AC 59 ms 8220 KB
subtask1_special04.txt AC 60 ms 8232 KB
subtask1_special05.txt AC 59 ms 8224 KB
subtask1_special06.txt AC 44 ms 4108 KB
subtask1_special07.txt AC 46 ms 4124 KB
subtask1_special08.txt AC 45 ms 4120 KB
subtask1_special09.txt AC 45 ms 4136 KB
subtask1_special10.txt AC 45 ms 4136 KB
subtask1_special11.txt AC 44 ms 3624 KB
subtask1_special12.txt AC 43 ms 3228 KB
subtask1_special13.txt AC 41 ms 3100 KB
subtask1_special14.txt AC 27 ms 1980 KB
subtask1_special15.txt AC 60 ms 8224 KB