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
Submission Time |
|
Task |
C - 有向グラフ |
User |
funcsr |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2326 Byte |
Status |
AC |
Exec Time |
19 ms |
Memory |
4864 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 |
1 ms |
1024 KB |
subtask0_sample_02.txt |
AC |
1 ms |
1024 KB |
subtask0_sample_03.txt |
AC |
1 ms |
1024 KB |
subtask0_sample_04.txt |
AC |
1 ms |
1024 KB |
subtask1_manual01.txt |
AC |
1 ms |
1024 KB |
subtask1_manual02.txt |
AC |
1 ms |
1024 KB |
subtask1_manual03.txt |
AC |
1 ms |
1024 KB |
subtask1_manual04.txt |
AC |
1 ms |
1024 KB |
subtask1_manual05.txt |
AC |
1 ms |
1024 KB |
subtask1_manual06.txt |
AC |
1 ms |
1024 KB |
subtask1_manual07.txt |
AC |
1 ms |
1024 KB |
subtask1_manual08.txt |
AC |
1 ms |
1024 KB |
subtask1_random01.txt |
AC |
2 ms |
1152 KB |
subtask1_random02.txt |
AC |
2 ms |
1024 KB |
subtask1_random03.txt |
AC |
4 ms |
1280 KB |
subtask1_random04.txt |
AC |
2 ms |
1152 KB |
subtask1_random05.txt |
AC |
2 ms |
1024 KB |
subtask1_special01.txt |
AC |
2 ms |
1024 KB |
subtask1_special02.txt |
AC |
3 ms |
1280 KB |
subtask1_special03.txt |
AC |
14 ms |
3072 KB |
subtask1_special04.txt |
AC |
19 ms |
4864 KB |
subtask1_special05.txt |
AC |
16 ms |
3328 KB |
subtask1_special06.txt |
AC |
10 ms |
1792 KB |
subtask1_special07.txt |
AC |
12 ms |
2048 KB |
subtask1_special08.txt |
AC |
10 ms |
1792 KB |
subtask1_special09.txt |
AC |
10 ms |
1792 KB |
subtask1_special10.txt |
AC |
11 ms |
1792 KB |
subtask1_special11.txt |
AC |
11 ms |
1664 KB |
subtask1_special12.txt |
AC |
10 ms |
1536 KB |
subtask1_special13.txt |
AC |
12 ms |
1408 KB |
subtask1_special14.txt |
AC |
2 ms |
1024 KB |
subtask1_special15.txt |
AC |
16 ms |
3328 KB |