#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr <<__func__<<":"<<" [" << #x << "] = ["; _print(x); /*cerr << "\e[39m" << endl;*/
#else
#define dbg(x...)
#endif
#define ll long long
#define ld long double
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<ll,ll>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (int)x.size()
#define endl '\n'
const ll N = 25000, INF = 1e18, MOD = 1e9+7;
const int S = 26;
int t = 0;
struct Node {
//vector<int> nxt;
int nxt[S];
bool is_word = 0;
int height = 0;
Node() {
//nxt.assign(S, -1);
for (int i = 0; i < S; i++) nxt[i] = -1;
}
};
//vector<Node> trie(1);
Node trie[N * S];
void add_str(string& s) {
int v = 0;
for (int i = 0; i < sz(s); i++) {
int cur = s[i] - 'a';
if (trie[v].nxt[cur] == -1) {
trie[v].nxt[cur] = ++t;
//trie[v].nxt[cur] = sz(trie);
//trie.emplace_back();
}
v = trie[v].nxt[cur];
trie[v].height = max(trie[v].height, sz(s) - i);
if (i == sz(s) - 1) {
trie[v].is_word = 1;
}
}
}
void solve() {
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
add_str(a[i]);
}
vector<char> ans;
function<void(int)> dfs = [&] (int v) {
if (trie[v].is_word) ans.emplace_back('P');
int mx = -1, who = -1;
for (int i = 0; i < S; i++) {
int u = trie[v].nxt[i];
if (u == -1) continue;
if (mx < trie[u].height) {
mx = trie[u].height;
who = i;
}
}
//dbg(char('a' + who), mx)
for (int i = 0; i < S; i++) {
int u = trie[v].nxt[i];
if (u == -1 || i == who) continue;
ans.emplace_back(char('a' + i));
dfs(u);
}
if (who != -1) {
ans.emplace_back(char('a' + who));
dfs(trie[v].nxt[who]);
}
ans.emplace_back('-');
};
dfs(0);
while (ans.back() == '-') ans.pop_back();
cout << sz(ans) << endl;
for (int i = 0; i < sz(ans); i++) {
cout << ans[i] << endl;
}
// READ AT THE BOTTOM PLS!
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n = 1?)
* READ CONSTRAINTS
* reset variables?
* STAY ORGANIZED
*/
/*
Suppose I did find such a solution, what would it look like?
What characteristics it would have?
Can we toy around with such a solution so that it remains optimal?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
71508 KB |
Output is correct |
| 2 |
Correct |
27 ms |
71428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
71516 KB |
Output is correct |
| 2 |
Correct |
32 ms |
71508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
71460 KB |
Output is correct |
| 2 |
Correct |
27 ms |
71508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
71452 KB |
Output is correct |
| 2 |
Correct |
32 ms |
71420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
71548 KB |
Output is correct |
| 2 |
Correct |
29 ms |
71580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
71636 KB |
Output is correct |
| 2 |
Correct |
32 ms |
71664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
71844 KB |
Output is correct |
| 2 |
Correct |
38 ms |
72240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
72400 KB |
Output is correct |
| 2 |
Correct |
33 ms |
72212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
73400 KB |
Output is correct |
| 2 |
Correct |
105 ms |
75520 KB |
Output is correct |
| 3 |
Correct |
72 ms |
74552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
73256 KB |
Output is correct |
| 2 |
Correct |
121 ms |
76264 KB |
Output is correct |
| 3 |
Correct |
73 ms |
74988 KB |
Output is correct |
| 4 |
Correct |
104 ms |
76104 KB |
Output is correct |
