Submission #1295250
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define CIN_ONLY if(1)
struct cww{cww(){
CIN_ONLY{
ios::sync_with_stdio(false);cin.tie(0);
}
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
for(auto &it:v)is>>it;
return is;
}
//Decomposition of Strongly Connected Components
//KYOURENKETSU SEIBUN BUNKAI
/*
comp[v]: component id of vertex v
node[k]: vertexes in component k
edge[k]: link edges from component k to component t!=k
*/
typedef vector<int> V;
typedef vector<V> VV;
typedef VV Graph;
#define ITR(i,v) for(auto & i :(v))
struct SCC{
Graph e,r_e;
V vs;
int size;
V comp;
VV node;
Graph edge;
void dfs(int v){
comp[v]=0;
ITR(u,e[v])if(comp[u]<0)dfs(u);
vs.pb(v);
}
void rdfs(int v,int k){
comp[v]=k;
ITR(u,r_e[v])if(comp[u]<0)rdfs(u,k);
}
void decomposition(){
comp.resize(size);
fill(ALL(comp),-1);
vs.reserve(size);
REP(v,size)if(comp[v]<0)dfs(v);
reverse(ALL(vs));
fill(ALL(comp),-1);
int k=0;
ITR(v,vs)if(comp[v]<0)rdfs(v,k++);
node.resize(k);
edge.resize(k);
REP(v,size){
node[comp[v]].pb(v);
for(auto& u : e[v]){
if(!isSameComponents(v,u)){
edge[comp[v]].pb(comp[u]);
}
}
}
size=k;
}
bool isSameComponents(int a,int b){
return comp[a]==comp[b];
}
SCC(Graph& in){
size=in.size();
e=in;
r_e.resize(size);
REP(v,size)ITR(u,e[v])r_e[u].pb(v);
decomposition();
}
};
string inf="z";
int main(){
inf[0]++;
int n,m,k;
cin>>n>>m>>k;
vector<char> C(n);
cin>>C;
Graph g(n);
REP(i,m){
int a,b;
cin>>a>>b;
g[a-1].pb(b-1);
}
SCC scc(g);
int G=scc.size;
vector<string> S(G);
REP(i,G){
for(auto &v:scc.node[i])S[i].pb(C[v]);
sort(ALL(S[i]));
}
vector<vector<string>> dp(G);
REC(void,int) dfs=[&](int v){
if(dp[v].size()>0)return;
dp[v].resize(k+1,inf);
for(auto &u:scc.edge[v]){
dfs(u);
REP(i,k+1)REP(b,i+1){
int a=i-b;
if(dp[u][b]!=inf&&S[v].size()>=a){
string t=S[v].substr(0,a)+dp[u][b];
chmin(dp[v][i],t);
}
}
}
REP(i,k+1)if(i<=S[v].size())chmin(dp[v][i],S[v].substr(0,i));
};
REP(i,G)dfs(i);
string res=inf;
REP(i,G)chmin(res,dp[i][k]);
if(res==inf)cout<<-1<<endl;
else cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 有向グラフ |
User |
btk15049 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3266 Byte |
Status |
AC |
Exec Time |
66 ms |
Memory |
9472 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 |
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 |
AC |
8 ms |
640 KB |
subtask1_random02.txt |
AC |
3 ms |
384 KB |
subtask1_random03.txt |
AC |
21 ms |
1024 KB |
subtask1_random04.txt |
AC |
7 ms |
512 KB |
subtask1_random05.txt |
AC |
2 ms |
384 KB |
subtask1_special01.txt |
AC |
1 ms |
384 KB |
subtask1_special02.txt |
AC |
2 ms |
640 KB |
subtask1_special03.txt |
AC |
15 ms |
3072 KB |
subtask1_special04.txt |
AC |
36 ms |
6784 KB |
subtask1_special05.txt |
AC |
65 ms |
9472 KB |
subtask1_special06.txt |
AC |
28 ms |
3456 KB |
subtask1_special07.txt |
AC |
13 ms |
1920 KB |
subtask1_special08.txt |
AC |
27 ms |
3456 KB |
subtask1_special09.txt |
AC |
31 ms |
3328 KB |
subtask1_special10.txt |
AC |
28 ms |
3328 KB |
subtask1_special11.txt |
AC |
22 ms |
2688 KB |
subtask1_special12.txt |
AC |
20 ms |
2176 KB |
subtask1_special13.txt |
AC |
18 ms |
1792 KB |
subtask1_special14.txt |
AC |
1 ms |
384 KB |
subtask1_special15.txt |
AC |
66 ms |
9472 KB |