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 |
|
|
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 |