#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500500;
int trie[N][26];
bool ch[N];
int mxd[N];
string ans = "";
void dfs_sz(int v) {
for (int i = 0;i < 26;i++) {
if (trie[v][i]) {
dfs_sz(trie[v][i]);
mxd[v] = max(mxd[v], mxd[trie[v][i]] + 1);
}
}
}
void dfs(int v, int keep) {
if (ch[v]) ans += "P";
if (keep) {
int big = -1;
for (int i = 0;i < 26;i++) {
if (trie[v][i]) {
if (mxd[trie[v][i]] == mxd[v] - 1) big = i;
}
}
for (int i = 0;i < 26;i++) {
if (trie[v][i] && trie[v][i] != trie[v][big]) {
ans += i + 'a';
dfs(trie[v][i], 0);
}
}
if (big != -1) {
ans += big + 'a';
dfs(trie[v][big], 1);
}
return;
}
for (int i = 0;i < 26;i++) {
if (trie[v][i]) {
ans += i + 'a';
dfs(trie[v][i], 0);
}
}
ans += "-";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
int idx = 0;
for (int i = 1;i <= n;i++) {
string s;
cin >> s;
int now = 0;
for (auto& x : s) {
if (!trie[now][x - 'a'])
trie[now][x - 'a'] = ++idx;
now = trie[now][x - 'a'];
}
ch[now] = 1;
}
dfs_sz(0);
dfs(0, 1);
cout << ans.size() << '\n';
for (auto& x : ans) cout << x << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2512 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3164 KB |
Output is correct |
2 |
Correct |
2 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5296 KB |
Output is correct |
2 |
Correct |
12 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
9704 KB |
Output is correct |
2 |
Correct |
6 ms |
4188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
20184 KB |
Output is correct |
2 |
Correct |
80 ms |
43020 KB |
Output is correct |
3 |
Correct |
43 ms |
23324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
16380 KB |
Output is correct |
2 |
Correct |
97 ms |
50700 KB |
Output is correct |
3 |
Correct |
53 ms |
26364 KB |
Output is correct |
4 |
Correct |
76 ms |
47952 KB |
Output is correct |