Submission #1501137
Source Code Expand
// {{{ Templates
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz:" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
os << "(" << p.first << "," << p.second
<< ")";
return os;
}
constexpr ll MOD = (ll)1e9 + 7LL;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;
// }}}
struct DGraph {
using T = int;
DGraph(const int v) : V{v}
{
edge.resize(v);
rev_edge.resize(v);
}
struct Edge {
Edge(const int from, const int to, const T cost) : from{from}, to{to}, cost{cost} {}
const int from;
const int to;
const T cost;
bool operator<(const Edge& e) const
{
return cost != e.cost ? cost < e.cost : to < e.to;
}
};
void addEdge(const int from, const int to, const T cost)
{
edge[from].push_back(Edge{from, to, cost});
rev_edge[to].push_back(Edge(to, from, cost));
}
vector<vector<Edge>> edge;
vector<vector<Edge>> rev_edge;
const int V;
};
void dfs1_scc(const DGraph& g, const int s, vector<int>& st, vector<bool>& used)
{
assert(s < g.V);
assert(used.size() == g.V);
used[s] = true;
for (const auto& e : g.edge[s]) {
if (not used[e.to]) {
dfs1_scc(g, e.to, st, used);
}
}
st.push_back(s);
}
void dfs2_scc(const DGraph& g, const int s, const int index, vector<int>& cmp, vector<bool>& used)
{
assert(s < g.V);
assert(index < g.V);
assert(cmp.size() == g.V);
cmp[s] = index;
used[s] = true;
for (const auto& e : g.rev_edge[s]) {
if (not used[e.to]) {
dfs2_scc(g, e.to, index, cmp, used);
}
}
};
int SCC(const DGraph& g, vector<int>& cmp)
{
assert(cmp.size() == g.V);
for (int i = 0; i < g.V; i++) {
cmp[i] = 0;
}
vector<int> st;
vector<bool> used(g.V, false);
for (int i = 0; i < g.V; i++) {
if (not used[i]) {
dfs1_scc(g, i, st, used);
}
}
for (int i = 0; i < g.V; i++) {
used[i] = false;
}
int comp = 0;
for (int i = 0; i < st.size(); i++) {
const int s = st[st.size() - i - 1];
if (not used[s]) {
dfs2_scc(g, s, comp++, cmp, used);
}
}
return comp;
}
void dfs_topo(const DGraph& g, const int s, vector<bool>& used, vector<int>& srt)
{
assert(s < g.V);
assert(used.size() == g.V);
if (not used[s]) {
used[s] = true;
for (const auto& e : g.edge[s]) {
dfs_topo(g, e.to, used, srt);
}
srt.push_back(s);
}
}
void TopologocalSort(const DGraph& g, vector<int>& srt)
{
srt.clear();
vector<bool> used(g.V, false);
for (int i = 0; i < g.V; i++) {
dfs_topo(g, i, used, srt);
}
reverse(srt.begin(), srt.end());
}
int n, m, k;
void dp_dfs(const DGraph& g, const int s, const int prev, const vector<int>& comp, const vector<string>& compst, vector<vector<string>>& dp, vector<bool>& compused, vector<bool>& visited, const vector<string>& dummy)
{
if (visited[s]) {
return;
}
visited[s] = true;
if (not compused[comp[s]]) {
if (prev == -1) {
for (int i = 0; i <= min(k, (int)compst[comp[s]].size()); i++) {
dp[comp[s]][i] = min(dp[comp[s]][i], compst[comp[s]].substr(0, i));
}
} else {
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= min(i, (int)compst[comp[s]].size()); j++) {
const string str = dp[comp[prev]][i - j] + compst[comp[s]].substr(0, j);
dp[comp[s]][i] = min(dp[comp[s]][i], str);
}
}
}
compused[comp[s]] = true;
}
for (const auto& e : g.edge[s]) {
const int to = e.to;
dp_dfs(g, to, s, comp, compst, dp, compused, visited, dummy);
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m >> k;
DGraph g(n);
vector<char> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g.addEdge(a, b, 1);
}
vector<int> comp(n);
const int compnum = SCC(g, comp);
vector<int> srt(n);
TopologocalSort(g, srt);
vector<string> compst(compnum);
for (int i = 0; i < n; i++) {
compst[comp[i]].push_back(c[i]);
}
for (int i = 0; i < compnum; i++) {
sort(compst[i].begin(), compst[i].end());
}
vector<string> dummy(k + 1);
for (int i = 1; i <= k; i++) {
dummy[i] = dummy[i - 1];
dummy[i].push_back('z' + 1);
}
vector<vector<string>> dp(compnum, vector<string>(k + 1)); // comp, kind
for (int i = 0; i < compnum; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = dummy[j];
}
}
vector<bool> compused(compnum, false);
vector<bool> visited(n, false);
for (const int s : srt) {
if (not visited[s]) {
dp_dfs(g, s, -1, comp, compst, dp, compused, visited, dummy);
}
}
string st = dummy[k];
for (int i = 0; i < compnum; i++) {
st = min(st, dp[i][k]);
}
for (const char ch : st) {
if (ch == 'z' + 1) {
cout << -1 << endl;
return 0;
}
}
cout << st << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 有向グラフ |
User |
pachicobue |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5980 Byte |
Status |
WA |
Exec Time |
48 ms |
Memory |
17920 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
256 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask0_sample_03.txt |
AC |
1 ms |
256 KB |
subtask0_sample_04.txt |
AC |
1 ms |
256 KB |
subtask1_manual01.txt |
AC |
1 ms |
256 KB |
subtask1_manual02.txt |
AC |
1 ms |
256 KB |
subtask1_manual03.txt |
AC |
1 ms |
256 KB |
subtask1_manual04.txt |
AC |
1 ms |
256 KB |
subtask1_manual05.txt |
AC |
1 ms |
256 KB |
subtask1_manual06.txt |
AC |
1 ms |
256 KB |
subtask1_manual07.txt |
AC |
1 ms |
256 KB |
subtask1_manual08.txt |
AC |
1 ms |
256 KB |
subtask1_random01.txt |
WA |
4 ms |
640 KB |
subtask1_random02.txt |
WA |
2 ms |
384 KB |
subtask1_random03.txt |
WA |
10 ms |
1408 KB |
subtask1_random04.txt |
WA |
4 ms |
640 KB |
subtask1_random05.txt |
AC |
2 ms |
384 KB |
subtask1_special01.txt |
AC |
1 ms |
512 KB |
subtask1_special02.txt |
AC |
2 ms |
512 KB |
subtask1_special03.txt |
AC |
11 ms |
3328 KB |
subtask1_special04.txt |
AC |
22 ms |
9088 KB |
subtask1_special05.txt |
AC |
35 ms |
17792 KB |
subtask1_special06.txt |
AC |
24 ms |
6144 KB |
subtask1_special07.txt |
AC |
12 ms |
2176 KB |
subtask1_special08.txt |
AC |
24 ms |
6144 KB |
subtask1_special09.txt |
AC |
24 ms |
6144 KB |
subtask1_special10.txt |
AC |
35 ms |
6144 KB |
subtask1_special11.txt |
AC |
22 ms |
4608 KB |
subtask1_special12.txt |
AC |
21 ms |
3712 KB |
subtask1_special13.txt |
AC |
21 ms |
3200 KB |
subtask1_special14.txt |
AC |
1 ms |
384 KB |
subtask1_special15.txt |
AC |
48 ms |
17920 KB |