Submission #1337985
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
char c[300], s[2];
vector<int>E[300], rE[300], G[300];
bool used[300];
vector<int>vs;
int cmp[300];
string t[300], dp[300][301], INF(301, 'z');
void dfs(int v) {
used[v] = true;
for (int u : E[v]) {
if (!used[u])dfs(u);
}
vs.push_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
cmp[v] = k;
for (int u : rE[v]) {
if(!used[u])rdfs(u, k);
}
}
string rec(int v, int k) {
if (dp[v][k] != "")return dp[v][k];
string res = INF, a;
for (int i = 0; i < min(k, (int)t[v].size() + 1); i++) {
for (int u : G[v]) {
res = min(res, rec(u, k - i) + a);
}
if (i < t[v].size())a += t[v][i];
}
if (a.size() == k)res = min(res, a);
return dp[v][k] = res;
}
int main() {
int n, m, K; scanf("%d%d%d", &n, &m, &K);
rep(i, n) {
scanf("%s", s); c[i] = s[0];
}
rep(i, m) {
int a, b; scanf("%d%d", &a, &b); a--; b--;
E[a].push_back(b); rE[b].push_back(a);
}
rep(i, n) {
if (!used[i])dfs(i);
}
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++);
}
rep(i, n) {
for (int u : E[i]) {
if (cmp[i] != cmp[u])G[cmp[u]].push_back(cmp[i]);
}
}
rep(i, n)t[cmp[i]] += c[i];
rep(i, k)sort(t[i].begin(), t[i].end());
string ans = INF;
rep(i, k)ans = min(ans, rec(i, K));
if (ans == INF)puts("-1");
else cout << ans << endl;
}
Submission Info
Submission Time
2017-06-09 20:33:40+0900
Task
C - 有向グラフ
User
autumn_eel
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1471 Byte
Status
AC
Exec Time
19 ms
Memory
4736 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:39:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n, m, K; scanf("%d%d%d", &n, &m, &K);
^
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s); c[i] = s[0];
^
./Main.cpp:44:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b); a--; b--;
^
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
4 ms
1024 KB
subtask1_random02.txt
AC
3 ms
1024 KB
subtask1_random03.txt
AC
5 ms
1024 KB
subtask1_random04.txt
AC
3 ms
1024 KB
subtask1_random05.txt
AC
2 ms
1024 KB
subtask1_special01.txt
AC
2 ms
1024 KB
subtask1_special02.txt
AC
2 ms
1024 KB
subtask1_special03.txt
AC
9 ms
3200 KB
subtask1_special04.txt
AC
14 ms
4736 KB
subtask1_special05.txt
AC
19 ms
1152 KB
subtask1_special06.txt
AC
13 ms
1024 KB
subtask1_special07.txt
AC
10 ms
2048 KB
subtask1_special08.txt
AC
14 ms
1024 KB
subtask1_special09.txt
AC
14 ms
1152 KB
subtask1_special10.txt
AC
13 ms
1152 KB
subtask1_special11.txt
AC
12 ms
1152 KB
subtask1_special12.txt
AC
12 ms
1152 KB
subtask1_special13.txt
AC
11 ms
1152 KB
subtask1_special14.txt
AC
2 ms
1024 KB
subtask1_special15.txt
AC
16 ms
1152 KB