Submission #1511810

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M, K;
char C[300];
vector<int> G[300], R[300];
vector<int> G2[300];

bool used[300];
int ord[300];
string T[300];

vector<int> vs;
void dfs(int x) {
  if (used[x]) return;
  used[x] = true;
  for (int t : G[x]) dfs(t);
  vs.pb(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);
  }
  //cout<<"dp("<<x<<","<<k<<") = "<< m<<" (t="<<T[x]<<")\n";
  return memo[x][k] = m;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> K;
  rep(i, N) cin >> C[i];
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].pb(b);
    R[b].pb(a);
  }
  int V = scc();
  rep(i, V) {
    string s = "";
    rep(x, N) if (ord[x] == i) s += C[x];
    sort(all(s));
    T[i] = s;
  }
  rep(x, N) {
    for (int t : G[x]) {
      if (ord[x] != ord[t]) G2[ord[x]].pb(ord[t]);
    }
  }
  rep(i, V) {
    sort(all(G2[i])); uniq(G2[i]);
  }

  string s = "~";
  rep(i, V) s = min(s, dp(i, K));
  if (s == "~") s = "-1";
  cout << s << "\n";
  return 0;
}

Submission Info

Judge Result