This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |