#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6;
int n, t, trie[maxn][26], exist[maxn], dp[maxn];
string s, ans;
void insert(string s)
{
int cur = 0;
for (int i = 0; i < (int)s.size(); i++)
{
int id = s[i]-'a';
if (!trie[cur][id]) trie[cur][id] = ++t;
cur = trie[cur][id];
}
exist[cur] = 1;
}
void precal(int u)
{
bool ok = 0;
for (int id = 0; id < 26; id++)
{
if (!trie[u][id]) continue;
ok = 1;
precal(trie[u][id]);
dp[u] = max(dp[u], dp[trie[u][id]]+1);
}
if (!ok) dp[u] = 1;
}
void dfs(int u)
{
if (exist[u])
{
ans += "P";
n--;
}
vector<pair<int, int>> v;
for (int id = 0; id < 26; id++)
if (trie[u][id]) v.push_back({dp[trie[u][id]], id});
sort(v.begin(), v.end());
for (int i = 0; i < (int)v.size(); i++)
{
int id = v[i].second;
if (!trie[u][id]) continue;
s += 'a'+id;
ans += 'a'+id;
dfs(trie[u][id]);
}
if (u == 0) return;
s.pop_back();
if (n) ans += "-";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
insert(s);
}
precal(0);
dfs(0);
cout << (int)ans.size() << '\n';
for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
2 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3164 KB |
Output is correct |
2 |
Correct |
3 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5212 KB |
Output is correct |
2 |
Correct |
13 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
11752 KB |
Output is correct |
2 |
Correct |
6 ms |
4188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
24316 KB |
Output is correct |
2 |
Correct |
89 ms |
46888 KB |
Output is correct |
3 |
Correct |
47 ms |
27636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18420 KB |
Output is correct |
2 |
Correct |
105 ms |
54628 KB |
Output is correct |
3 |
Correct |
54 ms |
30448 KB |
Output is correct |
4 |
Correct |
86 ms |
51980 KB |
Output is correct |