Submission #1474328


Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int V;
VI G[310], rG[310], vs;
VVI g;
bool used[310];
int cmp[310];
char c[310];

void add_edge(int from, int to) {
  G[from].PB(to);
  rG[to].PB(from);
}

void dfs(int v) {
  used[v] = true;
  // cout << "v:" << v << endl;
  for(int i: G[v]) {
    if(!used[i]) dfs(i);
  }
  // cout << v << endl;
  vs.PB(v);
}

void rdfs(int v, int k) {
  // cout << v << "," << k << endl;
  used[v] = true;
  cmp[v] = k;
  for(int i: rG[v]) {
    if(!used[i]) rdfs(i, k);
  }
}

int scc() {
  memset(used, 0, sizeof(used));
  vs.clear();
  REP(v, V) if(!used[v]) dfs(v);
  // cout << "vs:"; REP(i, vs.size()) cout << vs[i] << " "; cout << endl;
  memset(used, 0, sizeof(used));
  int k = 0;
  for(int i = vs.size() - 1; i >= 0; --i) {
    if(!used[vs[i]]) rdfs(vs[i], k++);
  }
  return k;
}

VVI getDAG() {
  int N = scc();
  VVI res(N);
  vector<set<int>> st(N);
  REP(i, V) st[cmp[i]].insert(i);
  REP(i, N) {
    set<int> out;
    for(const auto& v : st[i]) {
      for(const auto& to : G[v]) {
        out.insert(cmp[to]);
      }
    }
    for(const auto& to : out) {
      res[i].emplace_back(to);
    }
  }
  return res;
}

string s[310];
string dp[310][310];

signed main(void)
{
  int m, k;
  cin >> V >> m >> k;
  REP(i, V) cin >> c[i];
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    add_edge(a, b);
  }

  int n = scc();
  g = getDAG();
  REP(i, V) s[cmp[i]] += c[i];
  REP(i, n) sort(ALL(s[i]));
  // REP(i, g.size()) {
  //   cout << "i:" << i << " " << s[i] << " ";
  //   REP(j, g[i].size()) {
  //     cout << g[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  memset(used, false, sizeof(used));
  REP(v, n) {
    // cout << "v:" << v << endl;
    if(used[v]) continue;
    used[v] = true;
    vector<string> cp(k+1, "");
    FOR(i, 1, k+1) {
      REP(j, s[v].size()+1) {
        if(i < j) break;
        if(dp[v][i-j].size() != i-j) continue;
        if((int)cp[i].size() != i) {
          cp[i] = dp[v][i-j] + s[v].substr(0, j);
        } else {
          chmin(cp[i], dp[v][i-j] + s[v].substr(0, j));
        }
      }
    }
    // cout << "cp "; REP(i, k+1) cout << cp[i] << " "; cout << endl;
    REP(i, k+1) {
      if(cp[i].size() != i) continue;
      if(dp[v][i].size() != i) dp[v][i] = cp[i];
      else chmin(dp[v][i], cp[i]);
    }
    // cout << "dp "; REP(i, k+1) cout << dp[v][i] << " "; cout << endl;
    for(const auto& to : g[v]) {
      // cout << to << endl;
      REP(i, k+1) {
        if(dp[v][i].size() != i) continue;
        if(dp[to][i].size() != i) dp[to][i] = dp[v][i];
        else chmin(dp[to][i], dp[v][i]);
      }
      // cout << "to "; REP(i, k+1) cout << dp[to][i] << " "; cout << endl;
    }
  }

  string ans(k+1, 'z');
  REP(i, n) {
    // cout << dp[i][k] << endl;
    if((int)dp[i][k].size() != k) continue;
    chmin(ans, dp[i][k]);
  }
  if(ans == string(k+1, 'z')) cout << "-1" << endl;
  else cout << ans << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 有向グラフ
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3795 Byte
Status AC
Exec Time 21 ms
Memory 7168 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 2 ms 1024 KB
subtask0_sample_02.txt AC 2 ms 1024 KB
subtask0_sample_03.txt AC 2 ms 1024 KB
subtask0_sample_04.txt AC 2 ms 1024 KB
subtask1_manual01.txt AC 2 ms 1024 KB
subtask1_manual02.txt AC 2 ms 1024 KB
subtask1_manual03.txt AC 2 ms 1024 KB
subtask1_manual04.txt AC 2 ms 1024 KB
subtask1_manual05.txt AC 2 ms 1024 KB
subtask1_manual06.txt AC 2 ms 1024 KB
subtask1_manual07.txt AC 2 ms 1024 KB
subtask1_manual08.txt AC 2 ms 1024 KB
subtask1_random01.txt AC 3 ms 1152 KB
subtask1_random02.txt AC 2 ms 1024 KB
subtask1_random03.txt AC 4 ms 1792 KB
subtask1_random04.txt AC 3 ms 1152 KB
subtask1_random05.txt AC 2 ms 1024 KB
subtask1_special01.txt AC 2 ms 1152 KB
subtask1_special02.txt AC 3 ms 1152 KB
subtask1_special03.txt AC 10 ms 3072 KB
subtask1_special04.txt AC 15 ms 5888 KB
subtask1_special05.txt AC 21 ms 7168 KB
subtask1_special06.txt AC 13 ms 2816 KB
subtask1_special07.txt AC 10 ms 1920 KB
subtask1_special08.txt AC 13 ms 2816 KB
subtask1_special09.txt AC 13 ms 2816 KB
subtask1_special10.txt AC 13 ms 2816 KB
subtask1_special11.txt AC 12 ms 2304 KB
subtask1_special12.txt AC 12 ms 2048 KB
subtask1_special13.txt AC 13 ms 1920 KB
subtask1_special14.txt AC 2 ms 1024 KB
subtask1_special15.txt AC 18 ms 1152 KB