oj.uz

Submission #855173

# Submission time Handle Problem Language Result Execution time Memory
855173 2023-09-30T12:32:36 Z vjudge1 Type Printer (IOI08_printer) C++14
100 / 100
 88 ms 49420 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 9 ms 6488 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7660 KB Output is correct
2 Correct 4 ms 1884 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20208 KB Output is correct
2 Correct 69 ms 41692 KB Output is correct
3 Correct 30 ms 21500 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14332 KB Output is correct
2 Correct 88 ms 49420 KB Output is correct
3 Correct 39 ms 24308 KB Output is correct
4 Correct 59 ms 46736 KB Output is correct