AtCoder Regular Contest 030

Submission #1337985

Source codeソースコード

#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

Task問題 C - 有向グラフ
User nameユーザ名 autumn_eel
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1471 Byte
File nameファイル名
Exec time実行時間 19 ms
Memory usageメモリ使用量 4736 KB

Compiler messageコンパイルメッセージ

./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--;
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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