Submission #1645874


Source Code Expand

#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 300;
const int Mmax = 1000;
int N, M, K;
char C[Nmax];
int A[Mmax], B[Mmax];

void scc_visit(int n, vector<vector<int> > &graph, vector<bool> &visited, vector<int> &visit_nodes){
	if(visited[n]) return;
	visited[n] = true;
	for(int i=0; i<graph[n].size(); i++){
		scc_visit(graph[n][i], graph, visited, visit_nodes);
	}
	visit_nodes.push_back(n);
}

void scc_assign(int n, int r, vector<vector<int> > &graph, vector<int> &root){
	if(root[n] >= 0) return;
	root[n] = r;
	for(int i=0; i<graph[n].size(); i++){
		scc_assign(graph[n][i], r, graph, root);
	}
}

// perform strongly connected components decomposition
// root is the result, verteces in the same component have the same root
void scc(vector<vector<int> > &graph, vector<int> &root){
	root = vector<int>(graph.size(), -1);
	vector<bool> visited(graph.size());

	for(int i=0; i<graph.size(); i++){
		vector<int> visit_nodes;
		scc_visit(i, graph, visited, visit_nodes);
		for(int j=0; j<visit_nodes.size(); j++){
			scc_assign(visit_nodes[j], visit_nodes[j], graph, root);
		}
	}
}

void topological_sort_visit(int n, vector<vector<int> > &graph, vector<int> &visited, vector<int> &order){
	if(visited[n]) return;
	visited[n] = true;
	for(int i=0; i<graph[n].size(); i++){
		topological_sort_visit(graph[n][i], graph, visited, order);
	}
	order.push_back(n);
}

void topological_sort(vector<vector<int> > &graph, vector<int> &order){
	vector<int> visited(graph.size());
	order = vector<int>(graph.size());

	for(int i=0; i<graph.size(); i++){
		topological_sort_visit(i, graph, visited, order);
	}

	reverse(order.begin(), order.end());
}

int main(){
	cin >> N >> M >> K;
	for(int i=0; i<N; i++) cin >> C[i];
	for(int i=0; i<M; i++){
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}

	vector<vector<int> > graph(N);
	for(int i=0; i<M; i++){
		graph[A[i]].push_back(B[i]);
	}

	vector<int> root;
	scc(graph, root);

	//for(int i=0; i<N; i++){
	//	cout << root[i] << endl;
	//}

	vector<int> root_nodes;
	for(int i=0; i<N; i++){
		root_nodes.push_back(root[i]);
	}

	sort(root_nodes.begin(), root_nodes.end());
	int n_components = unique(root_nodes.begin(), root_nodes.end())-root_nodes.begin();
	vector<int> root_nodes_index(N);
	for(int i=0; i<n_components; i++){
		root_nodes_index[root_nodes[i]] = i;
	}

	vector<vector<int> > component_graph(n_components);
	for(int i=0; i<M; i++){
		if(root[A[i]] == root[B[i]]) continue;
		component_graph[root_nodes_index[root[A[i]]]].push_back(root_nodes_index[root[B[i]]]);
	}

	for(int i=0; i<n_components; i++){
		sort(component_graph[i].begin(), component_graph[i].end());
		component_graph[i] = vector<int>(component_graph[i].begin(),
				unique(component_graph[i].begin(), component_graph[i].end()));

		//for(int j=0; j<component_graph[i].size(); j++){
		//	cout << component_graph[i][j] << ' ';
		//}
		//cout << endl;
	}

	vector<string> component_chars(n_components);
	for(int i=0; i<N; i++){
		component_chars[root_nodes_index[root[i]]].push_back(C[i]);
	}

	for(int i=0; i<n_components; i++){
		sort(component_chars[i].begin(), component_chars[i].end());
		//cout << i << " " << component_chars[i] << endl;
	}

	vector<int> topological_order;
	topological_sort(component_graph, topological_order);

	vector<vector<string> > dp(n_components, vector<string>(K+1));
	for(int i=n_components-1; i>=0; i--){
		int n = topological_order[i];
		for(int j=1; j<=K; j++){
			if(j <= component_chars[n].size()) dp[n][j] = component_chars[n].substr(0, j);
			//cout << dp[n][j] << " " << n << " " << j << endl;
			for(int k=0; k<component_graph[n].size(); k++){
				int m = component_graph[n][k];
				for(int l=0; l<=min(j, (int)component_chars[n].size()); l++){
					string s = component_chars[n].substr(0, l) + dp[m][j-l];
					//cout << s << " " << n << " " << j << " " << m << " " << l << endl;
					if(s.size() != j) continue;
					if(dp[n][j] == "" || s < dp[n][j]){
						dp[n][j] = s;
					}
				}
			}
		}
	}

	//for(int i=n_components-1; i>=0; i--){
	//	for(int j=1; j<=K; j++){
	//		cout << dp[i][j] << (j==K ? '\n' : ' ');
	//	}
	//}

	string ans = dp[0][K];
	for(int i=0; i<n_components; i++){
		if(dp[i][K] == "") continue;
		ans = min(dp[i][K], ans);
	}

	if(ans == "") cout << -1 << endl;
	else cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task C - 有向グラフ
User emak
Language C++ (G++ 4.6.4)
Score 0
Code Size 4456 Byte
Status WA
Exec Time 22 ms
Memory 7296 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 4
AC × 21
WA × 11
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 512 KB
subtask1_random02.txt AC 2 ms 384 KB
subtask1_random03.txt WA 22 ms 640 KB
subtask1_random04.txt WA 3 ms 384 KB
subtask1_random05.txt AC 2 ms 256 KB
subtask1_special01.txt AC 2 ms 384 KB
subtask1_special02.txt AC 2 ms 512 KB
subtask1_special03.txt AC 10 ms 2688 KB
subtask1_special04.txt AC 17 ms 5632 KB
subtask1_special05.txt AC 21 ms 7168 KB
subtask1_special06.txt WA 2 ms 384 KB
subtask1_special07.txt WA 2 ms 256 KB
subtask1_special08.txt WA 2 ms 384 KB
subtask1_special09.txt WA 2 ms 384 KB
subtask1_special10.txt WA 2 ms 384 KB
subtask1_special11.txt WA 2 ms 384 KB
subtask1_special12.txt WA 2 ms 384 KB
subtask1_special13.txt WA 1 ms 384 KB
subtask1_special14.txt AC 1 ms 256 KB
subtask1_special15.txt AC 22 ms 7296 KB