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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
#define trie __trie__
struct trie{
struct trie_node{
int nxt[26];
bool leaf;
int mxheight;
trie_node(){
memset(nxt, -1, sizeof(nxt));
leaf = 0;
mxheight = 0;
}
};
vector <trie_node> a;
trie(){
a.assign(1, trie_node());
}
void insert(const string &s){
int u = 0;
Fora(c, s){
if (a[u].nxt[c - 'a'] == -1){
a.emplace_back();
a[u].nxt[c - 'a'] = isz(a) - 1;
}
u = a[u].nxt[c - 'a'];
}
a[u].leaf = 1;
}
void dfs_height(int u){
For(i, 0, 26){
if (a[u].nxt[i] != -1){
dfs_height(a[u].nxt[i]);
a[u].mxheight = max(a[u].mxheight, a[a[u].nxt[i]].mxheight + 1);
}
}
}
void dfs(int u, string &sans){
if (a[u].leaf){
sans += 'P';
}
int j = max_element(a[u].nxt, a[u].nxt + 26, [&](int u, int v){
if (v == -1){
return false;
}
if (u == -1){
return true;
}
return a[u].mxheight < a[v].mxheight;
}) - a[u].nxt;
For(i, 0, 26){
if (i == j){
continue;
}
if (a[u].nxt[i] != -1){
sans += (char)(i + 'a');
dfs(a[u].nxt[i], sans);
sans += '-';
}
}
if (a[u].nxt[j] != -1){
sans += (char)(j + 'a');
dfs(a[u].nxt[j], sans);
sans += '-';
}
}
} cac;
const int N = 2e4 + 5e3 + 5;
int n;
string s[N];
string sans;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
ForE(i, 1, n){
cin >> s[i];
}
ForE(i, 1, n){
cac.insert(s[i]);
}
cac.dfs_height(0);
cac.dfs(0, sans);
while (!sans.empty() and sans.back() == '-'){
sans.pop_back();
}
cout << isz(sans) << endl;
Fora(c, sans){
cout << c << endl;
}
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# | 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... |