Submission #855173

#	Time	Username	Problem	Language	Result	Execution time	Memory
855173		vjudge1	Type Printer (IOI08_printer)	C++14	100 / 100	88 ms	49420 KiB

printer

#include <bits/stdc++.h>
using namespace std;
const int SIG = 26, NN = 25000;
struct Node {
	int ch[SIG];
	bool mark, end;
} T[NN * 20];
int sz = 0;
void insert(const string& s) {
	int u = 0;
	for (char c : s) {
		int d = c - 'a', &cu = T[u].ch[d];
		if (!cu)
			cu = ++sz;
		u = cu;
	}
	T[u].end = true;
}
void dfs(int u, string& ans) {
	const Node& x = T[u];
	if (x.end)
		ans += 'P'; // 单词结尾, 打印
	int mi = -1;
	for (int i = 0; i < SIG; ++i) {
		int v = x.ch[i];
		if (!v)
			continue;
		if (T[v].mark)
			mi = i; // 先不走最长的串
		else
			ans += i + 'a', dfs(v, ans); // 走其它串
	}
	if (mi != -1) // 走最长串
		ans += mi + 'a', dfs(x.ch[mi], ans);
	ans += '-';
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	string s, l;
	for (int i = 0; i < n; ++i) {
		cin >> s, insert(s);
		if (s.length() > l.length())
			l = s;
	}
	for (size_t i = 0, u = 0; i < l.size(); i++) // 标记最长的单词
		u = T[u].ch[l[i] - 'a'], T[u].mark = true;
	s.clear(), dfs(0, s);
	while (s.back() == '-')
		s.pop_back(); // 最后的字符全部删掉
	cout << s.size() << "\n";
	for (char c : s)
		cout << c << "\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10