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