Submission #1571222

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;  //頂点数
int M;  //辺の数
int K;  //回収するアルファベットの数
char C[300];    //頂点に書かれているアルファベット
vector<int> G[300]; //グラフの辺
vector<int> R[300]; //グラフの逆辺
vector<int> G2[300];

bool used[300];
vector<int> vs; //帰りがけ順の並び
int ord[300];   //属する強連結成分のトポロジカル順序
string T[300];

void dfs(int x)
{
    if (used[x]) return;
    used[x] = true;
    for (int t : G[x]) dfs(t);
    vs.push_back(x);
}

void rdfs(int x, int k) {
    if (used[x]) return;
    used[x] = true;
    ord[x] = k;
    for (int t : R[x]) rdfs(t, k);
}

int scc()
{
    REP(i,N) used[i] = false;
    REP(i,N) dfs(i);
    REP(i,N) used[i] = false;
    int k = 0;
    for (int i=vs.size()-1; i>=0; i--) {
        if (!used[vs[i]]) rdfs(vs[i], k++);
    }
    return k;
}

string memo[300][301];
string dp(int x, int k)
{
    if (memo[x][k] != "") return memo[x][k];
    if (k == 0) return "";

    int len = T[x].length();
    string m = "~";
    for (int d=0; d<=min(len,k); d++) {
        string prefix = T[x].substr(0, d);
        string e = "~";
        if (k == d) e = "";
        else {
            for (int t : G2[x]) {
                string o = dp(t, k - d);
                if (o != "~") e = min(e, o);
            }
        }
        if (e != "~") m = min(m, prefix + e);
    }

    return memo[x][k] = m;
}

signed main()
{
    cin >> N >> M >> K;
    REP(i,N) cin >> C[i];
    REP(i,M) {
        int a, b;   //頂点aから頂点bに移動できる辺がある
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        R[b].push_back(a);
    }

    int V = scc();  //強連結成分分解。Vは強連結成分の個数
    REP(i,V) {
        string s = "";
        REP(x,N) if (ord[x] == i) s += C[x];
        sort(s.begin(), s.end());
        T[i] = s;
    }
    REP(x,N) {
        for (int t : G[x]) {
            if (ord[x] != ord[t]) G2[ord[x]].push_back(ord[t]);
        }
    }
    REP(i,V) {
        sort(G2[i].begin(), G2[i].end());
        uniq(G2[i]);
    }

    string s = "~";
    REP(i,V) s = min(s, dp(i, K));
    if (s == "~") s = "-1";
    cout << s << endl;
}

Submission Info

Judge Result