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

Judge Result